引言

参照的是左程云的课程：https://space.bilibili.com/8888480/lists/3509640?type=series

本笔记是class046的内容，总结了构建前缀信息的技巧来解决子数组相关问题。这类问题通过预处理前缀信息，结合哈希表等数据结构，可以将原本O(n²)或更高时间复杂度的问题优化到O(n)。

前置知识

在学习前缀信息技巧之前，需要掌握以下基础知识：

讲解026 - 哈希表的用法
数组基础操作和累加和概念
基本的数学推导能力

046【必备】构建前缀信息的技巧-解决子数组相关问题

核心解题思路

前缀和的基本概念

前缀和是一种预处理技巧，通过构建辅助数组来快速计算任意区间的累加和：

# 前缀和数组构建
s = [0] * (len(nums) + 1)  # 比原数组长1
for i in range(len(nums)):
    s[i + 1] = s[i] + nums[i]

# 区间[left, right]的和 = s[right+1] - s[left]

前缀信息 + 哈希表的套路

解决子数组问题的通用套路：

构建前缀信息：根据问题需求构建前缀和、前缀状态等
设计哈希表：存储前缀信息的位置或次数
遍历求解：边计算前缀信息，边查询哈希表更新答案

题目一：前缀和数组 - 快速区间求和

问题描述

设计一个支持快速查询数组区间和的数据结构。

测试链接：https://leetcode.cn/problems/range-sum-query-immutable/

核心思想

通过预计算前缀和，实现O(1)时间复杂度的范围和查询：
通过预计算前缀和，实现O(1)时间复杂度的范围和查询。

创建一个比原数组长1的前缀和数组 s。
s[i] 存储原数组 nums 从 0 到 i-1 位置的累加和。
nums 数组从 left 到 right 的范围和，
就可以通过 s[right+1] - s[left] 快速得到。
s[right+1] 是 0…right 的和
s[left] 是 0…left-1 的和
两者相减即为 left…right 的和。

算法实现

import sys

arr = []
n, aim = 0, 0
# key : 某个前缀和
# value : 这个前缀和最早出现的位置
prefix_sum_map = {}

def compute():
    """
    通过预计算前缀和，实现O(1)时间复杂度的范围和查询。
    """
    prefix_sum_map.clear()
    # 重要 : 0这个前缀和，在-1位置（一个数字也没有的时候），就存在了
    # 这可以正确处理从0开始的子数组
    prefix_sum_map[0] = -1
    ans = 0
    current_sum = 0 
    for i in range(n):
        current_sum += arr[i]
        # 查找是否存在一个 j，使得 0..j 的前缀和为 current_sum - aim
        if (current_sum - aim) in prefix_sum_map:
            j = prefix_sum_map[current_sum - aim]
            ans = max(ans, i - j)
        
        # 只记录每个前缀和第一次出现的位置
        if current_sum not in prefix_sum_map:
            prefix_sum_map[current_sum] = i
    return ans

def main():
    """
    处理输入和输出的主函数
    """
    global n, aim, arr
    # 高效读取所有输入行
    lines = sys.stdin.readlines()
    if not lines:
        return
        
    line_iter = iter(lines)
    while True:
        try:
            line = next(line_iter)
            if not line: break
            
            n, aim = map(int, line.strip().split())
            arr_line = next(line_iter)
            arr = list(map(int, arr_line.strip().split()))
            
            print(compute())
            
        except StopIteration:
            break

if __name__ == "__main__":
    main()

算法分析

预处理时间复杂度：O(n)
查询时间复杂度：O(1)
空间复杂度：O(n)

题目二：累加和为给定值的最长子数组

问题描述

给定一个无序数组arr，其中元素可正、可负、可0。给定一个整数aim，求arr所有子数组中累加和为aim的最长子数组长度。

测试链接：https://www.nowcoder.com/practice/36fb0fd3c656480c92b569258a1223d5

核心思想

使用前缀和 + 哈希表记录每个前缀和最早出现的位置：

遍历数组，计算到当前位置 i 的前缀和 s
如果存在位置 j，使得 (0...i的前缀和) - (0...j的前缀和) = aim
即 s - (0...j的前缀和) = aim，所以需要查找前缀和为 s - aim 的位置
为了让子数组最长，j 应该尽可能小，所以只记录每个前缀和首次出现的位置

算法实现

import sys
from collections import defaultdict

def compute():
    """
    计算累加和为aim的最长子数组长度
    """
    prefix_sum_map = {}
    # 重要：0这个前缀和，在-1位置（一个数字也没有的时候）就存在了
    # 这可以正确处理从0开始的子数组
    prefix_sum_map[0] = -1
    
    ans = 0
    current_sum = 0 
    for i in range(n):
        current_sum += arr[i]
        # 查找是否存在一个 j，使得 0..j 的前缀和为 current_sum - aim
        if (current_sum - aim) in prefix_sum_map:
            j = prefix_sum_map[current_sum - aim]
            ans = max(ans, i - j)
        
        # 只记录每个前缀和第一次出现的位置
        if current_sum not in prefix_sum_map:
            prefix_sum_map[current_sum] = i
    return ans
### 类似上一题那样定义main和继续处理

算法分析

时间复杂度：O(n)
空间复杂度：O(n)
核心技巧：记录最早位置 + 前缀和差值

题目三：累加和为给定值的子数组个数

问题描述

返回无序数组中累加和为给定值的子数组个数。

测试链接：https://leetcode.cn/problems/subarray-sum-equals-k/

核心思想

与寻找最长子数组类似，但哈希表存储的是前缀和出现的次数：

prefix_sum_map[s - aim] 的值代表有多少个合法的子数组可以在 i 位置结尾
累加这些次数得到总的子数组个数

算法实现

from typing import List
from collections import defaultdict

class Solution:
    def subarraySum(self, nums: List[int], aim: int) -> int:
        """
        计算累加和为aim的子数组个数。
        核心思想：
        与寻找最长子数组类似，但哈希表的用途不同。
        1. 这里的哈希表 `prefix_sum_map` 存储的是 {前缀和 -> 该前缀和出现的次数}。
        2. 遍历数组，计算到位置 `i` 的前缀和 `s`。
        3. 同样，我们寻找 `s - aim` 这个目标前缀和。
        4. 哈希表中 `prefix_sum_map[s - aim]` 的值，就代表了有多少个合法的子数组
           可以在 `i` 位置结尾。我们将这个次数累加到 `ans` 中。
        5. 遍历完 `i` 后，更新 `s` 在哈希表中的出现次数。
        """
        # key: 前缀和, value: 该前缀和出现的次数
        # 使用 defaultdict 可以简化代码
        prefix_sum_map = defaultdict(int)
        
        # 0这个前缀和，在没有任何数字的时候，已经有1次了
        # 空集也算一个子集
        prefix_sum_map[0] = 1
        
        ans = 0
        current_sum = 0
        for num in nums:
            # current_sum : 0...i前缀和
            current_sum += num
            
            # 查找有多少个 j 满足 0..j 的前缀和为 current_sum - aim
            count = prefix_sum_map[current_sum - aim]
            ans += count
            
            # 更新当前前缀和的出现次数
            prefix_sum_map[current_sum] += 1
            
        return ans

算法分析

时间复杂度：O(n)
空间复杂度：O(n)
核心技巧：记录出现次数 + 累加计数

题目四：正数和负数个数相等的最长子数组

问题描述

给定一个无序数组arr，其中元素可正、可负、可0。求arr所有子数组中正数与负数个数相等的最长子数组的长度。

测试链接：https://www.nowcoder.com/practice/545544c060804eceaed0bb84fcd992fb

核心思想

问题转化：将原数组进行转换，正数变为1，负数变为-1，0保持为0。在新数组中，如果一个子数组的累加和为0，就意味着其中1和-1的数量相等，对应原数组中正数和负数数量相等。

之后算法就和”累加和为0的最长子数组”完全一样。

算法实现

def compute():
    """
    核心思想：
    1. 这个问题可以转化为“累加和为0的最长子数组长度”问题。
    2. 将原数组进行转换：正数变为1，负数变为-1，0保持为0。
    3. 在新数组中，如果一个子数组的累加和为0，
       就意味着其中的1和-1的数量相等，这正好对应原数组中正数和负数数量相等。
    4. 之后，算法就和“累加和为aim的最长子数组”完全一样，只是这里的aim固定为0。
    """
    prefix_sum_map.clear()
    prefix_sum_map[0] = -1
    ans = 0
    current_sum = 0
    for i in range(n):
        current_sum += transformed_arr[i]
        
        # 寻找目标前缀和 (current_sum - 0)
        if current_sum in prefix_sum_map:
            j = prefix_sum_map[current_sum]
            ans = max(ans, i - j)
            
        if current_sum not in prefix_sum_map:
            prefix_sum_map[current_sum] = i
            
    return ans

def main():
    global n, transformed_arr
    lines = sys.stdin.readlines()
    if not lines:
        return
        
    line_iter = iter(lines)
    while True:
        try:
            line = next(line_iter)
            if not line: break
            
            n = int(line.strip())
            arr_line = next(line_iter)
            original_arr = list(map(int, arr_line.strip().split()))
            
            # 转换数组
            transformed_arr = [0] * n
            for i in range(n):
                num = original_arr[i]
                if num > 0:
                    transformed_arr[i] = 1
                elif num < 0:
                    transformed_arr[i] = -1
                # 0 保持为 0
            
            print(compute())
            
        except StopIteration:
            break

if __name__ == "__main__":
    main()

算法分析

时间复杂度：O(n)
空间复杂度：O(n)
核心技巧：问题转化 + 前缀和

题目五：表现良好的最长时间段

问题描述

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。当员工一天中的工作小时数大于8小时的时候，那么这一天就是劳累的一天。表现良好的时间段，意味在这段时间内，「劳累的天数」是严格大于不劳累的天数。请你返回表现良好时间段的最大长度。

测试链接：https://leetcode.cn/problems/longest-well-performing-interval/

核心思想

问题转化：将 >8 小时的天记为 +1，<=8 小时的天记为 -1。问题变成了”求和为正数的最长子数组长度”。

关键处理：

如果当前前缀和 > 0，说明从开头到当前位置整个时间段都表现良好
如果前缀和 <= 0，需要找到最早的位置 j，使得 j+1 到 i 的子数组和 > 0
这等价于寻找前缀和为 current_sum - 1 的最早位置

算法实现

from typing import List

class Solution:
    def longestWPI(self, hours: List[int]) -> int:
        """
        核心思想：
        1. 将问题进行转换：将 >8 小时的天记为 +1，<=8 小时的天记为 -1。
           问题就变成了“求和为正数的最长子数组长度”。
        2. 使用前缀和与哈希表。我们遍历数组，计算当前的前缀和 `current_sum`。
        3. 哈希表 `prefix_sum_map` 存储 {前缀和 -> 该和首次出现的位置}。
        4. 如果当前前缀和 `current_sum` > 0，说明从开头到当前位置的整个时间段都是
           表现良好的，长度为 `i + 1`，这是一个候选答案。
        5. 如果 `current_sum` <= 0，我们需要找到一个最早的位置 `j`，使得 `j+1` 到 `i` 的
           子数组和 > 0。这等价于 `current_sum - prefix_sum[j] > 0`，
           即 `current_sum > prefix_sum[j]`。
           为了使 `i - j` 最长，我们需要 `j` 最早，并且 `prefix_sum[j]` 尽可能小。
           我们寻找 `current_sum - 1` 这个前缀和最早出现的位置，因为它能保证
           `prefix_sum[j]` 严格小于 `current_sum`，从而找到一个候选的更长子数组。
        """
        # 某个前缀和，最早出现的位置
        prefix_sum_map = {}
        # 0这个前缀和，最早出现在-1，一个数也没有的时候
        prefix_sum_map[0] = -1
        
        ans = 0
        current_sum = 0
        for i, h in enumerate(hours):
            current_sum += 1 if h > 8 else -1
            
            # 如果当前前缀和 > 0，说明从0到i的整个子数组都是一个解
            if current_sum > 0:
                ans = i + 1
            else:
                # current_sum <= 0
                # 我们寻找是否存在一个更早的前缀和，值为 current_sum - 1
                # 如果存在，就能构成一个和为1的子数组，这也是一个解
                if (current_sum - 1) in prefix_sum_map:
                    ans = max(ans, i - prefix_sum_map[current_sum - 1])
            
            # 只记录每个前缀和第一次出现的位置，因为我们要找的是最早的位置
            if current_sum not in prefix_sum_map:
                prefix_sum_map[current_sum] = i
                
        return ans

算法分析

时间复杂度：O(n)
空间复杂度：O(n)
核心技巧：转化为正数和问题 + 特殊查找逻辑

题目六：使数组和能被P整除

问题描述

给你一个正整数数组 nums，请你移除最短子数组（可以为空），使得剩余元素的和能被 p 整除。不允许将整个数组都移除。请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1。

测试链接：https://leetcode.cn/problems/make-sum-divisible-by-p/

核心思想

关键观察：设总和为 total，我们需要移除一个子数组使得 (total - 子数组和) % p = 0。

设 mod = total % p，则需要移除的子数组和满足 子数组和 % p = mod。

使用前缀和余数 + 哈希表记录最晚出现的位置（为了让子数组最短）

算法实现

from typing import List

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        """
        核心思想：
        1. 首先计算整个数组的和对 p 取模，得到 `mod`。
           如果 `mod == 0`，则无需移除任何元素，返回 0。
        2. 我们的目标是移除一个子数组，其和对 p 取模的结果也等于 `mod`。
           这样 `(总和 - 子数组和) % p` 就会等于 `(mod - mod) % p = 0`。
        3. 问题转化为：寻找和对 p 取模为 `mod` 的最短子数组。
        4. 使用前缀和与哈希表。哈希表 `prefix_mod_map` 存储 {前缀和模p -> 该模值最晚出现的位置}。
           我们需要最晚的位置，是为了让 `i - j` 这个子数组长度最短。
        5. 遍历数组，计算到 `i` 的前缀和模 `p` 的值 `current_mod`。
        6. 我们需要寻找一个 `j`，使得 `(i...j)` 子数组的和模 `p` 为 `mod`。
           这等价于 `(prefix_mod[i] - prefix_mod[j-1]) % p == mod`。
           变形得 `prefix_mod[j-1] == (current_mod - mod + p) % p`。
        7. 我们在哈希表中查找这个目标 `find` 值，如果找到，就更新最短子数组长度。
        """
        # 整体余数
        mod = sum(nums) % p
        
        # 如果总和本身就能被p整除，无需移除
        if mod == 0:
            return 0
        
        # key : 前缀和%p的余数
        # value : 最晚出现的位置
        prefix_mod_map = {0: -1}
        ans = len(nums)
        
        current_mod = 0
        for i, num in enumerate(nums):
            # 0...i这部分的余数
            current_mod = (current_mod + num) % p
            
            # 我们要找的目标前缀和余数 find
            # find = (current_mod - mod) % p
            # +p 是为了处理负数情况
            find = (current_mod - mod + p) % p
            
            if find in prefix_mod_map:
                ans = min(ans, i - prefix_mod_map[find])
            
            # 存入当前前缀和余数出现的位置
            prefix_mod_map[current_mod] = i
            
        # 如果ans等于原数组长度，说明我们必须移除整个数组，按题意返回-1
        return ans if ans < len(nums) else -1

算法分析

时间复杂度：O(n)
空间复杂度：O(p)，最多存储p个不同的余数
核心技巧：取模运算 + 最晚位置

题目七：每个元音包含偶数次的最长子串

问题描述

给你一个字符串 s，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’ 在子字符串中都恰好出现了偶数次。

测试链接：https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/

核心思想

状态压缩：用5位二进制数表示五个元音字母出现次数的奇偶性。

例如：01100 表示 ‘e’ 和 ‘i’ 出现了奇数次，’a’,’o’,’u’出现了偶数次
如果两个位置的状态码相同，说明中间子串中每个元音都出现了偶数次

关键是找到相同状态码的最远距离。

算法实现

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        """
        核心思想：
        1. 我们只关心五个元音字母'a,e,i,o,u'出现次数的奇偶性。
           这可以用一个5位的二进制数（状态码/bitmask）来表示。
           例如，二进制 `01100` 表示 'e' 和 'i' 出现了奇数次，'a','o','u'出现了偶数次。
        2. 遍历字符串，维护一个从开头到当前位置的`status`状态码。
           遇到一个元音，就用异或(XOR)操作翻转其对应的位。
        3. 问题转化为：找到两个位置 `i` 和 `j`，使得它们的前缀状态码相同。
           如果 `prefix_status[i] == prefix_status[j]`，那么 `j+1` 到 `i` 的子串中，
           所有元音的奇偶性变化都抵消了，即每个元音都出现了偶数次。
        4. 我们需要找到最长的这样的子串，即最大化 `i - j`。
        5. 使用一个数组 `status_map` 记录每个状态码第一次出现的位置。
           `status_map[status] = earliest_index`。
        6. 初始化 `status_map[0] = -1`，表示初始状态（0次，偶数）出现在-1位置。
        """
        n = len(s)
        # 用一个数组来存储每种状态第一次出现的位置
        # 状态码范围是 0 (00000) 到 31 (11111)
        status_map = [-2] * 32 #-2是初始值，表示这个状态码没有出现过
        
        # 初始状态0 (所有元音都是偶数次0) 出现在-1位置
        status_map[0] = -1
        
        ans = 0
        status = 0
        vowel_map = {'a': 0, 'e': 1, 'i': 2, 'o': 3, 'u': 4}

        for i, char in enumerate(s):
            # status : 0....i-1字符串上，aeiou的奇偶性
            
            # 检查当前字符是否为元音，并更新状态
            if char in vowel_map:
                move = vowel_map[char] # 在vowel_map里看，a是0，e是1，i是2，o是3，u是4
                status ^= (1 << move) # status是0...i-1字符串上，aeiou的奇偶性，用异或操作翻转其对应的位
            
            # status: 0....i字符串上，aeiou的奇偶性，是个五位的二进制数
            
            # 检查当前状态是否之前出现过
            if status_map[status] != -2:
                # 如果出现过，计算长度并更新最大值
                ans = max(ans, i - status_map[status])
            else:
                # 如果是第一次出现，记录当前位置
                status_map[status] = i
                
        return ans

算法分析

时间复杂度：O(n)
空间复杂度：O(1)，状态数组固定大小32
核心技巧：状态压缩 + 位运算

核心套路总结

1. 前缀信息构建模板

# 基础前缀和
prefix_sum = [0] * (n + 1)
for i in range(n):
    prefix_sum[i + 1] = prefix_sum[i] + nums[i]

# 前缀状态（如奇偶性、余数等）
prefix_state = initial_state
for i in range(n):
    prefix_state = update_state(prefix_state, nums[i])
    # 处理当前状态

2. 哈希表设计策略

问题类型	哈希表存储内容	选择策略
最长子数组	{前缀信息 → 最早位置}	只存首次出现
最短子数组	{前缀信息 → 最晚位置}	覆盖存储
子数组计数	{前缀信息 → 出现次数}	累加计数

3. 边界条件处理

# 重要：处理从0开始的子数组
hash_map[initial_value] = -1

# 避免重复计算
if condition_to_update:
    hash_map[key] = value

4. 问题转化技巧

# 正负数相等 → 转化为累加和为0
transform = lambda x: 1 if x > 0 else (-1 if x < 0 else 0)

# 工作时间 → 转化为劳累天数大于非劳累天数
transform = lambda x: 1 if x > 8 else -1

# 元音奇偶性 → 状态压缩
state ^= (1 << vowel_index)  # 异或翻转对应位

复杂度分析总结

题目类型	时间复杂度	空间复杂度	核心数据结构
前缀和查询	O(1) 查询	O(n)	前缀和数组
最长子数组	O(n)	O(n)	哈希表
子数组计数	O(n)	O(n)	哈希表
状态压缩	O(n)	O(1)	固定数组

学习建议

1. 掌握核心思想

理解前缀信息的作用：将子数组问题转化为两个前缀的差值问题
掌握哈希表的不同用法：位置记录 vs 次数统计
熟练运用问题转化技巧

2. 注意实现细节

初始状态的正确设置（如 map[0] = -1）
哈希表更新时机的选择
边界条件的处理

3. 练习变形题目

不同的累加和目标值
不同的转化规则
多种约束条件的组合

4. 优化技巧

状态压缩减少空间占用
合理选择数据结构
避免不必要的重复计算

通过掌握前缀信息 + 哈希表的解题套路，可以高效解决各种子数组相关问题。关键在于正确构建前缀信息，合理设计哈希表存储策略，以及灵活运用问题转化技巧。