【算法】前缀和

数组前缀和

例题：

1. 和为K的子数组

/*
求数组的前缀和数组pre
然后求满足pre[i]-pre[j]==k的个数，即为答案
在求前缀和时边记录每个前缀和出现的次数，用map记录
那么对于以i结尾的数组找出pre[j]=pre[i]-k的个数累加起来。
*/
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0;
        unordered_map<int, int> mmp;
        mmp[0] = 1;
        int pre = 0;

        for(int i = 0; i < nums.size(); i++)
        {
            pre += nums[i];
            ans += mmp[pre - k];
            mmp[pre] += 1;
        }

        return ans;
        
    }
};

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

我们令 $P[i] = \textit{nums}[0] + \textit{nums}[1] + \ldots + \textit{nums}[i]$。那么每个连续子数组的和 $\textit{sum}(i, j)$ 就可以写成 $P[j] - P[i-1]$（其中 $0 < i < j$）的形式。此时，判断子数组的和能否被 k 整除就等价于判断 $(P[j] - P[i-1]) \bmod k == 0$，根据 同余定理，只要 $P[j] \bmod k == P[i-1] \bmod k$，就可以保证上面的等式成立。

因此我们可以考虑对数组进行遍历，在遍历同时统计答案。当我们遍历到第 $i$ 个元素时，我们统计以 $i$ 结尾的符合条件的子数组个数。我们可以维护一个以前缀和模 $k$ 的值为键，出现次数为值的哈希表 $\textit{record}$，在遍历的同时进行更新。这样在计算以 i 结尾的符合条件的子数组个数时，根据上面的分析，答案即为 $[0..i-1]$ 中前缀和模 k 也为 $P[i] \bmod k$ 的位置个数，即 $\textit{record}[P[i] \bmod k]$。

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> record = {{0, 1}};
        int sum = 0, ans = 0;
        for (int elem: nums) {
            sum += elem;
            // 注意 C++ 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
            int modulus = (sum % k + k) % k;
            if (record.count(modulus)) {
                ans += record[modulus];
            }
            ++record[modulus];
        }
        return ans;
    }
};

3. 每个元音包含偶数次的最长子字符串
4. 最美子字符串的数目