前缀和与哈希表综合应用

前缀和和哈希表的综合应用非常重要，今天我来总结一下

0X00 题目特征

最重要的特征就是「连续子数组」这一特征，在以前我可能会使用双端队列去做，但是发现有些题目不可证明。

碰到这个「连续子数组」这一特征你大概要想到三种思路：

• dp
• 前缀和与哈希表
• 双端队列

0X01 算法思想

首先我们知道前缀和有这么一个思想：sums[i] - sums[j] 就可以得到 [j+1, i] （包含左右端点）的和的信息。

现在我们有这么一个基础问题：560. 和为K的子数组

题目大致意思是：我们要找到所有和为 K 的所有子数组。

假设数组为 A，应用前缀和知识，我们可以求出以任意节点结尾的前缀和。也就是说，我们只需要遍历任意节点之前的前缀和，就能求出以任意节点为结尾的子数组的和。这样做的时间复杂度就是妥妥的 。

但是，如果我们用一个 map 记录所有的前缀，只需要计算我们需要的前缀，再去 map 里面找。这样的时间复杂度就是 。

基于这个思想我们来做四道题：

0X02 相关题目

560. 和为K的子数组

from collections import Counter

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums = [0] + nums
        c, sums = Counter(), [0] * (1+n)
        c[0] = 1
        for i in range(1, n+1): sums[i] = sums[i-1] + nums[i]
        res = 0
        for i in range(1, n+1):
            v = sums[i]
            t = v - k
            if t in c: res += c[t]
            c[v] += 1

        return res 

974. 和可被 K 整除的子数组

from collections import Counter
class Solution:
    def subarraysDivByK(self, a: List[int], k: int) -> int:
        n = len(a)
        sums, a = [0] * (n+1), [0] + a
        c = Counter()
        c[0] = 1
        res = 0
        for i in range(1, n+1): sums[i] = sums[i-1] + a[i]

        for i in range(1, n+1):
            s = sums[i]
            t = s % k
            if t in c: res += c[t]
            c[t] += 1
        
        return res

        

1248. 统计「优美子数组」

from collections import Counter
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        sums = [0] * (1+n)
        for i in range(1, 1+n): 
            sums[i] = sums[i-1]
            if nums[i-1] & 1:
                sums[i] = sums[i-1] + 1
        c = Counter()
        c[0] = 1
        res = 0
        for i in range(1, 1+n):
            v = sums[i]
            t = v - k
            if t in c: res += c[t]
            c[v] += 1
        
        return res

1371. 每个元音包含偶数次的最长子字符串

class Solution:
    def findTheLongestSubstring(self, s: str) -> int:
        n = len(s)
        sums, m, res = [0] * (1+n), {}, 0
        m[0] = 0
        for i in range(1, n+1):
            sums[i] = sums[i-1]
            c  = s[i-1]
            if c == 'a':
                sums[i] ^= 1
            elif c == 'e':
                sums[i] ^= 1 << 1
            elif c == 'i':
                sums[i] ^= 1 << 2
            elif c == 'o':
                sums[i] ^= 1 << 3
            elif c == 'u':
                sums[i] ^= 1 << 4
            t = sums[i]
            if t in m:
                res = max(res, i - m[t])
            else:
                m[t] = i
        
        return res

每个题的思想基本一致，除了最后一题有些小技巧外，并没有什么特别的地方

0X02 注意事项

• 一定要注意 map 初始化的时候，0 值的确定