前缀和：针对一个给定的数列A，它的前缀和数列定义如下： $gif.latex?S%5Bi%5D%20%3D%20%5Csum%5Climits_%7Bk%3D0%7D%5Climits%5E%7Bi%7DA%5Bk%5D$ （这里采用和c或者pyhton相同的从0开始的下标方式，以便于和编程进行对照）。

前缀和的计算有一个良好的特性，即不是每个前缀和都需要独立计算，前后有依赖关系，如下所示： $gif.latex?S%5Bi%5D%20%3D%20S%5Bi-1%5D%20+%20A%5Bi%5D$ ，这样的话针对数组（本文中不追求严格，数列和数组视为可以互换的名词）A，它的所有的前缀和可以在一次从左到右的遍历中以O(n)（而不是O(n**2)!）的时间复杂度计算得出。

前缀和的最基本的应用是用于计算数组中的子数组（定义为数组中一段连续区间构成的数组视为原数组的子数组）和，比如说要计算从下标j+1到下标i之间的子数组的和，可以基于前缀和进行如下计算而得：

$gif.latex?%5Csum%5Climits_%7Bk%3Dj+1%7D%5Climits%5E%7Bk%3Di%7D%20A%5Bk%5D%20%3D%20S%5Bi%5D%20-%20S%5Bj%5D$

前缀和与哈希表相结合对于有些算法问题的求解非常适合。以下以难度按循序渐进的方式介绍几道leetcode问题的求解，大家可以从体会到"前缀和+哈希表"这把小飞刀的强大之处。

2. 560. 和为 K 的子数组

2.1 问题描述

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2
示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

1 <= nums.length <= 2 * 10**4
-1000 <= nums[i] <= 1000
-10**7 <= k <= 10**7

2.2 方法1：枚举

令S[j,i]表示从nums[j]到nums[i]的子数组和。

最粗暴的方式是二维遍历所有可能的(j,i)组合（时间复杂度是 $gif.latex?O%28n%5E2%29$ ），计算所有各种组合的部分和S[j,i]，考虑到计算S[j,i]的复杂度也是 $gif.latex?O%28n%29$ ，所以总的时间复杂度是 $gif.latex?O%28n%5E3%29$ .

进一步，针对特定的j，它的所有部分和S[j,i]（针对不同的i：j<=i<=N-1）的计算不是相互独立的。比如说， $gif.latex?S%5Bj%2Ci%5D%3D%20S%5Bj%2Ci-1%5D+nums%5Bi%5D$ 。所以可以以一次前向遍历计算出针对某个j所有的S[j,i](i:j<=i<=N-1)。这样的话，时间复杂度可以简化为 $gif.latex?O%28n%5E2%29$ 。而针对j的遍历中，只需要记录一个到当前i位置的累加和，不同j的遍历是串行而且相互独立的，因为空间复杂度为 $gif.latex?O%281%29$ 。

代码如下：


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        cnt = 0
        for start in range(len(nums)):
            partsum = 0
            for end in range(start,len(nums)):
                partsum = partsum + nums[end]
                if partsum == k:
                    cnt = cnt + 1
                    # break
        return cnt

这个方案提交到leetcode会发生超时错误。。。

2.3 方法2：前缀和+哈希表

方法一的瓶颈在于对每个 i，我们需要枚举所有的 j （（或者，对每一个起始点j，要遍历所有的可能的终点i））来判断子数组和是否符合条件，这一步是否可以优化呢？答案是可以的。

定义 pre[i] 为 [0..i] 里所有数的和，则 pre[i] 可以由 pre[i−1] 递推而来，即：

$gif.latex?pre%5Bi%5D%3Dpre%5Bi-1%5D+nums%5Bi%5D$

那么“[j..i] 这个子数组和为 k”这个条件我们可以转化为

$gif.latex?pre%5Bi%5D-pre%5Bj-1%5D%3D%3Dk$

简单移项可得符合条件的下标j 需要满足

$gif.latex?pre%5Bj-1%5D%3D%3Dpre%5Bi%5D-k$

所以我们考虑以 i 结尾的和为 k 的连续子数组个数时只要统计满足以下条件的j的个数：

0<=j<=i
pre[j]==pre[i]−k

由于只关心个数，而不关心j的实际值是什么，所以我们可以建立哈希表hmap，以前缀和的值为key，该前缀和值出现的次数为value，这样我们在考察子数组结束位置为i的情况时，只要查询hmap[pre[i]-key]即可用O(1)的复杂度查询出结束位置为i的满足“其和为k”条件的子数组个数。

哈希表hmap的创建可以在从左到右遍历过程中建立，这个需要O(n)的复杂度。而如上所示查询针对每个位置i的满足条件的子数组数只需要O(1)的复杂度，因此总的只需要O(n)的时间复杂度。需要存储一张哈希表，空间复杂度为O(n)。

代码如下：


    def subarraySum(self, nums: List[int], k: int) -> int:
 
        cnt = 0
        h   = defaultdict(int)
        h[0] = 1
        presum = 0
        for i in range(len(nums)):
            presum = presum + nums[i]
            if presum-k in h:
                cnt = cnt + h[presum-k]
            h[presum] = h[presum] + 1
 
        return cnt

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

3.1 题目描述

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的（连续、非空）子数组的数目。

子数组是数组的连续部分。

示例 1：

输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
示例 2:

输入: nums = [5], k = 9
输出: 0

提示:

1 <= nums.length <= 3 * 10**4
-10**4 <= nums[i] <= 10**4
2 <= k <= 10**4

3.2 解题思路

本题与No560的差异仅在于从“子数组和等于k”的条件变为“子数组和能被k整除，也即为k的整数倍”。所有，只要两个前缀和对k同余的话，两者前缀和的差就表示一个能被k整除的子数组了。

所以，本题中，用(presume[i]%k)作为哈希表的key即可。

代码如下：


class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        cnt = 0
        hmap = defaultdict(int)
        hmap[0] = 1
        presum  = 0
        for i in range(len(nums)):
            presum = presum + nums[i]
            if presum % k in hmap:
                cnt = cnt + hmap[presum % k]
            hmap[presum % k] = hmap[presum % k] + 1
            
        return cnt

4. No0523. 连续的子数组和

4.1 问题描述

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

子数组大小至少为 2 ，且
子数组元素总和为 k 的倍数。
如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。

示例 1：

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。
示例 2：

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。
示例 3：

输入：nums = [23,2,6,4,7], k = 13
输出：false

提示：

1 <= nums.length <= 10**5
0 <= nums[i] <= 10**9
0 <= sum(nums[i]) <= 2**31 - 1
1 <= k <= 2**31 - 1

4.2 解题思路

本题有以下两点特征：

子数组长度不小于2
子数组和为k的倍数

第2点与No0974相同。所以可以在No974的解的基础上考察子数组长度不小于2的情况。此外，本题只要求是否存在而不要求统计个数，所以一旦找到满足条件即可提前退出。

在之前的几道题中，哈希表中没有体现子数组的位置信息。本题需要保留子数组的位置信息，因此哈希表中的value可以改为用一张表来保存子数组的位置信息（终止位置i）。

代码如下：


class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        # cnt = 0
        hmap = defaultdict(list)
        hmap[0] = [-1]
        presum  = 0
        for i in range(len(nums)):
            presum = presum + nums[i]
            if presum % k in hmap:
                print(hmap)
                # cnt = cnt + sum([(i-j)>=2 for j in hmap[presum % k]])
                for j in hmap[presum % k]:
                    if (i-j)>=2:
                        return True    
            # hmap[presum % k] = hmap[presum % k].append(i) # Incorrect!
            hmap[presum % k].append(i)            
            
        # return cnt          
        return False

需要注意的一点是列表的操作问题：

5. No0525. 连续数组

5.1 问题描述

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2:

输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

提示：

1 <= nums.length <= 10**5
nums[i] 不是 0 就是 1

5.2 解题思路

记pre[i]表示到nums[i]为止的前缀模2和。

创建哈希表，key={1的个数减去0的个数的差值}，value为对应key值的i值列表。一次从左到右的遍历以O(n)的时间复杂度创建哈希表。在此过程中，针对每个i，计算到i为止的满足条件的最长子数组。

代码如下：


class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        cnt = 0
        hmap = defaultdict(list)
        hmap[0] = [-1]
        pre  = 0
        maxlen = 0
        for i in range(len(nums)):
            pre = pre + (1 if nums[i]==1 else -1)
            if pre in hmap:
                print(hmap)
                maxlen = max(maxlen, i - min(hmap[pre]))
            hmap[pre].append(i)            
        return maxlen

5.3 优化

优化：事实上不需要存储对应key值的i值列表，而只需要记忆对应key值第一次出现的i即可，这样既节约存储又节约查询时间。

代码如下：


class Solution: 
 
    def findMaxLength(self, nums: List[int]) -> int:
        cnt = 0
        hmap = defaultdict(int)
        hmap[0] = -1
        pre  = 0
        maxlen = 0
        for i in range(len(nums)):
            pre = pre + (1 if nums[i]==1 else -1)
            if pre in hmap:
                #print(hmap)
                maxlen = max(maxlen, i - hmap[pre])
            else:
                hmap[pre] = i            
        return maxlen

6. No1590. 使数组和能被 P 整除

6.1 问题描述

给你一个正整数数组 nums，请你移除最短子数组（可以为空），使得剩余元素的和能被 p 整除。不允许将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组定义为原数组中连续的一组元素。

示例 1：

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。

示例 2：

输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。

示例 3：

输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。

示例 4：

输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。

示例 5：

输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0

提示：

1 <= nums.length <= 10**5
1 <= nums[i] <= 10**9
1 <= p <= 10**9

6.2 解题思路

要删掉的数的总和必定等于原数组总和S0对p同余，记k= S0%p。所以问题变为找最短的和与k同余（对p）的数组长度。转变后这个问题与No560、No974有一定的相似，但是却又不同。

本题中哈希表的键值用“pre = (pre + nums[i]) % p”，而对比查询时需要满足的条件是满足对p同余于k，即：

if ((pre - k) % p) in hmap:

minlen = min(minlen, i - hmap[((pre - k) % p)])

既然是关注最短子数组，那么哈希表中就应该是存储出现对应键值的最后那个i（参考525）。

代码如下：


class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:        
        k = sum(nums) % p
        if k==0:
            return 0
        hmap = defaultdict(int)
        hmap[0] = -1
        pre  = 0
        minlen = float('inf')
        for i in range(len(nums)):
            pre = (pre + nums[i]) % p
            # key = ((pre - k) % p)
            # print(k,i,pre,hmap)
            if ((pre - k) % p) in hmap:
                minlen = min(minlen, i - hmap[((pre - k) % p)])
            hmap[pre] = i            
        return minlen if minlen < len(nums) else -1

完整的代码请参考：https://github.com/chenxy3791/leetcode

另外，Leetcode每日一题总目录(动态更新。。。)也能找到一些leetcode解题笔记。

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】