一维前缀和

nums[left, right] 的和即 sum[right+1] - sum[left]

int n = nums.length; //原数组的长度
int[] sum = new int[n + 1]; //前缀和数组
for (int i = 1; i <= n; i++) {
    sum[i] = nums[i - 1] + sum[i - 1];
}

例题一

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

• 解法一： 利用前缀和数组，O（n^2）

public static int subarraySum(int[] nums, int k) {
    int size = nums.length, cnt = 0;
    //计算前缀和数组，该数组保存该元素之前的所有元素的和
    int[] preSum = new int[size + 1];
    preSum[0] = 0;
    for (int i = 1; i <= size; i++) {
        preSum[i] = preSum[i - 1] + nums[i - 1];
    }
    for (int i = 0; i < size; i++) {
        for (int j = i; j < size; j++) {
            if (preSum[j + 1] - preSum[i] == k) {
                cnt++;
            }
        }
    }
    return cnt;
}

• 解法二：前缀和 + 哈希表优化 O（N）

public int subarraySum(int[] nums, int k) {
    // key：前缀和，value：key 对应的前缀和的个数
    Map<Integer, Integer> preSumFreq = new HashMap<>();
    // 对于下标为 0 的元素，前缀和为 0，个数为 1
    preSumFreq.put(0, 1);

    int preSum = 0;
    int count = 0;
    for (int num : nums) {
        preSum += num;

        // 先获得前缀和为 preSum - k 的个数，加到计数变量里
        if (preSumFreq.containsKey(preSum - k)) {
            count += preSumFreq.get(preSum - k);
        }

        // 然后维护 preSumFreq 的定义
        preSumFreq.put(preSum, preSumFreq.getOrDefault(preSum, 0) + 1);
    }
    return count;
}

二维前缀和

若要求(a,b) -> (c,d)两点之间的方形区域的和

• 则sum = sum[c][d] - sum[c][b-1] - sum[a-1][d] + sum[a-1][b-1]
• 因前缀和数组边界扩大了1位，所以sum = sum[c+1][d+1] - sum[c+1][b] - sum[a][d+1] + sum[a][b], (其中，若超过前缀和数组的范围，需要修正下标min(max(n,x),0))

int m = nums[0].length;
int n = nums.length; //原数组的长度和宽度
int[][] sum = new int[n + 1][m + 1]; //前缀和数组
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        sum[i][j] = nums[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
    }
}

(a,b) -> (c,d)两点之间的方形区域的和为
sum[c+1][d+1] - sum[c+1][b] - sum[a][d+1] + sum[a][b]

例题

题目一

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

方法一：前缀和 + 状态压缩

我们先来考虑暴力方法怎么做。最直观的方法无非就是枚举所有子串，遍历子串中的所有字符，统计元音字母出现的个数。如果符合条件，我们就更新答案，但这样肯定会因为超时而无法通过所有测试用例。

再回顾一下上面的操作，其实每个子串对应着一个区间，那么有什么方法可以在不重复遍历子串的前提下，快速求出这个区间里元音字母出现的次数呢？答案就是前缀和，对于一个区间，我们可以用两个前缀和的差值，得到其中某个字母的出现次数。

我们对每个元音字母维护一个前缀和，定义pre[i][k]表示在字符串前i个字符中，第 k 个元音字母一共出现的次数。假设我们需要求出 [l,r] 这个区间的子串是否满足条件，那么我们可以用 pre[r][k]−pre[l−1][k]，在O(1)的时间得到第 k 个元音字母出现的次数。对于每一个元音字母，我们都判断一下其是否出现偶数次即可。

我们利用前缀和优化了统计子串的时间复杂度，然而枚举所有子串的复杂度仍需要 O(n^2)，不足以通过本题，还需要继续进行优化，避免枚举所有子串。我们考虑枚举字符串的每个位置 i ，计算以它结尾的满足条件的最长字符串长度。其实我们要做的就是快速找到最小的j∈[0,i)，满足 pre[i][k]−pre[j][k]（即每一个元音字母出现的次数）均为偶数，那么以 i 结尾的最长字符串 s[j+1,i] 长度就是 i−j。

有经验的读者可能马上就想到了利用哈希表来优化查找的复杂度，但是单单利用前缀和，我们无法找到 i 和 j 相关的恒等式，像优美子数组这道题我们是能明确知道两个前缀的差值是恒定的。那难道就没办法了么？其实不然，这道题我们还有一个性质没有充分利用：我们需要找的子串中，每个元音字母都恰好出现了偶数次。

偶数这个条件其实告诉了我们，对于满足条件的子串而言，两个前缀和 pre[i][k] 和 pre[j][k] 的奇偶性一定是相同的，因为小学数学的知识告诉我们：奇数减奇数等于偶数，偶数减偶数等于偶数。因此我们可以对前缀和稍作修改，从维护元音字母出现的次数改作维护元音字母出现次数的奇偶性。这样我们只要实时维护每个元音字母出现的奇偶性，那么 s[j+1,i] 满足条件当且仅当对于所有的 k，pre[i][k] 和 pre[j][k] 的奇偶性都相等，此时我们就可以利用哈希表存储每一种奇偶性（即考虑所有的元音字母）对应最早出现的位置，边遍历边更新答案。

题目做到这里基本上做完了，但是我们还可以进一步优化我们的编码方式，如果直接以每个元音字母出现次数的奇偶性为哈希表中的键，难免有些冗余，我们可能需要额外定义一个状态：

{
a: cnta, // a 出现次数的奇偶性
e: cnte, // e 出现次数的奇偶性
i: cnti, // i 出现次数的奇偶性
o: cnto, // o 出现次数的奇偶性
u: cntu // u 出现次数的奇偶性
}
将这么一个结构当作我们哈希表存储的键值，如果题目稍作修改扩大了字符集，那么维护起来可能会比较吃力。考虑到出现次数的奇偶性其实无非就两个值，0 代表出现了偶数次，1 代表出现了奇数次，我们可以将其压缩到一个二进制数中，第 k 位的 0 或 1 代表了第 k 个元音字母出现的奇偶性。举一个例子，假如到第 i 个位置，u o i e a 出现的奇偶性分别为 1 1 0 0 1，那么我们就可以将其压成一个二进制数 (11001)₂=(25)₁₀作为它的状态。这样我们就可以将 5 个元音字母出现次数的奇偶性压缩到了一个二进制数中，且连续对应了二进制数的 [(00000)₂,(11111)₂] 的范围，转成十进制数即 [0,31]。因此我们也不再需要使用哈希表，直接用一个长度为 32 的数组来存储对应状态出现的最早位置即可。

    public int findTheLongestSubstring(String s) {
        int n = s.length();
        int[] pos = new int[32];//储存不同奇偶性的最小index
        Arrays.fill(pos, -20000);//初始化凑数
        pos[0] = -1;
        int ans = 0, status = 0;
        for (int i = 0; i < n; i++) {
            switch (s.charAt(i)) {
                case 'a':
                    status ^= 1;
                    break;
                case 'e':
                    status ^= (1 << 1);
                    break;
                case 'i':
                    status ^= (1 << 2);
                    break;
                case 'o':
                    status ^= (1 << 3);
                    break;
                case 'u':
                    status ^= (1 << 4);
                    break;
            }
            if (pos[status] >= -1) {
                ans = Math.max(ans, i - pos[status]);
            } else {
                pos[status] = i;
            }
        }
        return ans;
    }