数组算法之“前缀和”

妖狐艹你老母 2023-02-13 03:53 137阅读 0赞

> 基于力扣算法题974. 和可被 K 整除的子数组  
> 基于[https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/solution/you-jian-qian-zhui-he-na-jiu-zai-ci-dai-ni-da-tong/][https_leetcode-cn.com_problems_subarray-sums-divisible-by-k_solution_you-jian-qian-zhui-he-na-jiu-zai-ci-dai-ni-da-tong]总结

### 1. 什么是前缀和 ###

*  前面的所有，再包括自己（数组 第 0 项 到 当前项 的 总和）

如果用一个数组 preSum 表示：

*  preSum\[0\]：数组A 第 0 项 到 第 0 项 的总和
 *  preSum\[1\]：数组A 第 0 项 到 第 1 项 的总和
 *  preSum\[2\]：数组A 第 0 项 到 第 2 项 的总和
 *  preSum\[3\]：数组A 第 0 项 到 第 3 项 的总和
 *  …… 于是有：  
    `preSum[i]=A[0]+A[1]+…+A[i]`
 *  数组某项，可以表示为相邻前缀和之差：  
    `A[i]=preSum[i]−preSum[i−1]`
 *  多项叠加，等号右边加减相消，得到通式：  
    `A[i]+…+A[j]=preSum[j]−preSum[i−1]`
 *  i 当然可以为 0，此时 i - 1 为 - 1，我们故意让 preSum\[-1\] 为 0，此时：  
    `A[0] +A[1]+…+A[j]=preSum[j]`
 *  预置这种不存在的情况，只是为了让 preSum\[0\] 能套用通式

### 前缀和数组 preSum 的项怎么求？ ###

*  当前项的前缀和 = 上一项的前缀和 + 当前项
 *  求出的 preSum 数组项，让它 mod K，mod 完再看哪两项相等，计数
 *  通式有 i、j两个变量，找出数组中所有相等的两项，需要 2 层循环去遍历 i,j
 *  时间复杂度：O(n^2) 。

### 整个流程 ###

*  预置 preSum\[-1\] = 0

1.  \-1 代表数组 A 的第 -1 项，即遍历数组 A 之前，map 提前放入 0:1，表示 求第 0 项前缀和之前，前缀和 mod K 等于 0 已经出现了 1 次
2.  这是违背现实的，但别纠结，只是为了求出第一个 preSumModK 而已

*  遍历数组 A 的每一项，求当前项的 preSumModK ，存入 map 中

1.  之前没有存过，则作为 key 存入，值为 1
2.  之前存过，则对应值 +1
3.  于是 map 就录入了各项对应的【前缀和 mod K】

*  边存 边查看已有的 key ，如果 map 中存在 key 等于 当前 preSumModK

1.  说明存在 之前求过的 preSumModK ，等于 当前 preSumModK
2.  把 key 对应的出现次数，累加给 count
3.  过去的某个前缀和，与当前前缀和搭配，差分出一个子数组
4.  出现过几次 ，就是有几个过去的前缀和，与当前前缀和，差分出几个满足条件的子数组

### 算法复杂度 ###

*  Time：O(n)
 *  Space：O(K)。 mod 的结果最多 K 种，哈希表最多存放 K 个键值对

### 代码 ###

class Solution { 
        public int subarraysDivByK(int[] A, int K) { 
            Map<Integer, Integer> record = new HashMap<>();
            record.put(0, 1);
            int sum = 0, ans = 0;
            for (int elem: A) { 
                sum += elem;
                // 注意 Java 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
                int modulus = (sum % K + K) % K;
                int same = record.getOrDefault(modulus, 0);
                ans += same;
                record.put(modulus, same + 1);
            }
            return ans;
        }
    }

#### 一看到“子数组和”，有必要马上想到“前缀和” ####

[https_leetcode-cn.com_problems_subarray-sums-divisible-by-k_solution_you-jian-qian-zhui-he-na-jiu-zai-ci-dai-ni-da-tong]: https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/solution/you-jian-qian-zhui-he-na-jiu-zai-ci-dai-ni-da-tong/