前缀和算法详解及 LeetCode 经典题目解析

代码实现：

public int pivotIndex(int[] nums) {
    int n = nums.length;
    if (n == 0) return -1;
    
    int[] f = new int[n]; // 前缀和
    int[] g = new int[n]; // 后缀和
    
    // 初始化边界
    f[0] = 0;
    g[n - 1] = 0;
    
    // 填充前缀和 f[i] = f[i-1] + nums[i-1]
    for (int i = 1; i < n; i++) {
        f[i] = f[i - 1] + nums[i - 1];
    }
    
    // 填充后缀和 g[i] = g[i+1] + nums[i+1]
    for (int i = n - 2; i >= 0; i--) {
        g[i] = g[i + 1] + nums[i + 1];
    }
    
    // 查找中心下标
    for (int i = 0; i < n; i++) {
        if (f[i] == g[i]) {
            return i;
        }
    }
    return -1;
}

2. 除自身以外数组的乘积

题目链接： LeetCode - Product of Array Except Self

题目解析

算法原理

解法一：暴力解法

每遍历到一个数组元素，就计算一次这个数组中，除该元素外的所有元素的乘积，得到的结果返回对应下标的 answer 中；时间复杂度 O(N^2)。

解法二：使用前缀积数组

我们可以先看 nums 数组其中一个位置 nums[i]： 在计算 nums[i] 时=前，我们可以预处理前缀积数组＆后缀积数组；当计算 nums[i] 时，我们就直接从预处理的数组拿值，就可以把计算 answer[i] 的时间复杂度降到 O(N)。

定义前缀积数组＆后缀积数组：

解析 f[i] ＆ g[i]

• f[i] 的含义＆递推公式：f[i] 表示 i 左侧所有元素的乘积。
• g[i] 的含义＆递推公式：g[i] 表示 i 右侧所有元素的乘积。

前缀和方法是典型的以空间换时间，预处理操作虽然多创建了一个数组，但是时间复杂度会得到质的提升。

使用前缀积数组＆后缀积数组 创建一个与 nums 数组同等规模的数组 answer： 而在填 answer 时，只需要计算 answer[i] = f[i-1] * g[i+1]。

处理细节问题 处理填 g[i] 时需要从后往前填外，还需要注意初始化问题：

代码实现：

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] answer = new int[n];
    
    int[] f = new int[n]; // 前缀积
    int[] g = new int[n]; // 后缀积
    
    // 初始化
    f[0] = 1;
    g[n - 1] = 1;
    
    // 计算前缀积
    for (int i = 1; i < n; i++) {
        f[i] = f[i - 1] * nums[i - 1];
    }
    
    // 计算后缀积
    for (int i = n - 2; i >= 0; i--) {
        g[i] = g[i + 1] * nums[i + 1];
    }
    
    // 计算结果
    for (int i = 0; i < n; i++) {
        answer[i] = f[i] * g[i];
    }
    
    return answer;
}

3. 和为 K 的子数组

题目链接： LeetCode - Subarray Sum Equals K

题目解析

算法原理

解法一：暴力解法

我们可以使用 O(N^2) 的时间复杂度枚举出所有子数组。当我们向后枚举到一个元素，使得和为 k 时，不能停止，也就需要向后继续枚举。直到枚举完最后一个元素，此时起始下标的枚举才完成。所以这道题是不能用双指针（滑动窗口）来做优化的，因为这道题的不具备单调性，每一个元素可正可负可为 0。

解法二：使用前缀和数组 + 哈希表

引入一个概念：以 i 位置为结尾的所有子数组。这个概念和暴力枚举相呼应，都是固定某一个位置，来枚举对应的情况。

因此，我们引入前缀和： 当枚举 i 位置时，其实我们已经知道以 i 位置为结尾的前缀和数组对应 i 位置的元素 sum[i] 是多少了。 所以，我们只需要找到一段区间的前缀和，让这个区间的前缀和等于 sum[i] - k 即可。 所以问题就转化成：在 [0, i-1] 区间内，有多少个前缀和为 sum[i] - k 的子数组。

但是，我们不能直接创建一个前缀和数组 sum，然后直接在 sum 中找前缀和为 sum[i] - k 的子数组，这样的做复杂度不如暴力解法。而哈希表用于快速查找某一个数，因此我们可以把前缀和塞入哈希表，然后把前缀和元素的出现个数，也放入哈希表中。

处理细节问题

1. 前缀和加入哈希表的时机：在计算 sum[i] 之前，先别把前缀和元素塞入哈希表中，哈希表只保存 [0, i - 1] 区间的前缀和元素。在计算 sum[i] 时，才把 i 位置的前缀和元素塞入哈希表。
2. 不用真的创建一个前缀和数组：只需要定义一个变量 sum，来标记一下 i - 1 位置的前缀和是多少即可。通过这个变量算出 dp[i]，再把这个变量更新成 dp[i] 即可。
3. 如果整个前缀和等于 k 呢？：如果我们在计算 i 位置的前缀和数组，发现 i 位置的前缀和的所有子数组中，只有整个数组之和才等于 k。根据刚刚的类比转化，程序就会去 [0, -1] 区间找和为 0 的前缀和数组，但是没有这个区间。所以对于这种情况，我们需要在进行正式的处理哈希表之前，先初始化一个元素 hash.put(0, 1)。

代码实现：

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1); // 初始化，处理从开头开始的子数组
    int count = 0;
    int sum = 0;
    
    for (int num : nums) {
        sum += num;
        if (map.containsKey(sum - k)) {
            count += map.get(sum - k);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    
    return count;
}

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

题目链接： LeetCode - Subarray Sums Divisible by K

题目解析

算法原理

解法一：暴力解法

暴力枚举出所有子数组，把所有子数组的和相加，再判断这些和中能被 k 整除的子数组。这道题的元素也就是可以<=0，不存在单调性，因此也不能使用滑动窗口解题。

补充知识

1. 同余定理：若 a % k = b % k，则 (a - b) % k = 0。
2. Java 负数取模修正：a % p (a < 0, p > 0) 结果为负数，修正方法为 (a % p + p) % p。

解法二：使用前缀和数组 + 哈希表

对于下面的绿色部分，就是我们要找的，在 [0, i - 1] 区域中的一个符合要求的子数组，而符合要求的子数组，要满足元素之和 % k = 0。 通过对绿色部分子数组的表达式的进行进一步的转换，我们发现了下面这个条件： 而 sum % k = x % k，也可以反过来推出绿色部分元素之和 % k = 0。 所以，问题就转换成：求在 [0, i - 1] 区间内，找到有多少给前缀和 x 通过与 k 取余，x%k=sum%k，进而就能反推出绿色部分的子数组。

处理细节问题 为了保证蓝线部分两边的取模结果都为正数，需要对结果进行修正，并且正负统一。 所以问题最终转换成：在 [0, i - 1] 区间内，找到前缀和被 k 取模后（也就是前缀和除以 k 后，得到的余数结果），余数结果等于 (sum % k + k) % k 的所有子数组。 我们不需要真的去创建前缀和数组，而是定义一个变量，这个变量也不是用来存前缀和，而是存前缀和除以 k 后，得到的余数，并且在哈希表中的 key 也表示这个余数。 并且，把余数加入到哈希表中的时机，也是在遍历一个元素，就插入一次。

总结

代码实现：

public int subarraysDivByK(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1); // 初始化
    int count = 0;
    int sum = 0;
    
    for (int num : nums) {
        sum += num;
        int remainder = (sum % k + k) % k; // 修正负数取模
        
        if (map.containsKey(remainder)) {
            count += map.get(remainder);
        }
        map.put(remainder, map.getOrDefault(remainder, 0) + 1);
    }
    
    return count;
}

5. 连续数组

题目链接： LeetCode - Contiguous Array

题目解析

算法原理

如果要统计 0 和 1 的个数，来求出相同数量的最长连续子数组，那么这道题还是有一定难度的。 但是，如果我们把 0 转换成 -1，就变成找出一段连续和为 0 的最长子数组，难度会降低很多。

解法：使用前缀和数组 + 子数组

处理细节问题

1. 哈希表中存什么？：对于哈希表的 key 和 val 存的是什么，我们可以查看上图，如果要算绿色区域的数组，我们就要知道两段红色区域的数组之和，如果两端红数组之和相等，绿数组即为我们所求。因此，我们需要下面的红数组的下标。
2. 什么时候存入哈希表？：当前 i 位置所绑定的前缀和要存入哈希表中，而当遍历完 [0, i - 1] 区域所有符合要求的子数组，并且返回最长的子数组时，我们再把当前 i 位置所绑定的前缀和存入哈希表。
3. 如果有重复的 <sum, i>，如何存？：如果出现重复的，只保留前面的 <sum, i> 即可（因为我们要找最长子数组，最早出现的索引差最大）。
4. 默认的前缀和为 0 该如何存？：在这道题里也有一个默认的前缀和为 0，之前的题都是 hash.put(0, 1)，表示如果整个区域之和等于所求的和，此时红数组为 [0, -1] 区域，把此时的红数组的前缀和初始化为 0，那么在哈希表中对应 key = 0 的 val+1。前面的题都是存 sum，以及 sum 出现次数，但是这个题每个桶的类型是 <sum, index>，所以这道题 hash.put(0, -1)。
5. 长度怎么算？：因为 sum 重复不会更新 index 对应的 val，长度 = 当前索引 i - 哈希表中存储的索引。

代码实现：

public int findMaxLength(int[] nums) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1); // 初始化，key 为前缀和，val 为索引
    int maxLen = 0;
    int sum = 0;
    
    for (int i = 0; i < nums.length; i++) {
        sum += (nums[i] == 0 ? -1 : 1);
        if (map.containsKey(sum)) {
            maxLen = Math.max(maxLen, i - map.get(sum));
        } else {
            map.put(sum, i);
        }
    }
    
    return maxLen;
}

6. 矩阵区域和

题目链接： LeetCode - Matrix Block Sum

题目解析

我们演示示例一求 answer 矩阵的一个元素 answer[0][0]： 并且，如果扩展的矩阵超出原始边界，超出的元素格子都不考虑：

算法原理

解法：使用二维前缀和

预处理前缀和数组 回顾快速求出二维前缀和递推公式：

处理细节问题

1. 处理边界情况：求 answer[i][j]，我们需要知道它在 mat 矩阵表示的区域，并且通过坐标表达出 answer[i][j] 向外扩展 k 个区域得到的矩阵，在 mat 矩阵所对应的区域。但是我们还需要处理可能出现的越界问题，设向上扩展的边界坐标 (x1, y1)，向下扩展的边界坐标为 (x2, y2)。如果 answer[i][j] 在向外扩展的时候，越过了 mat 矩阵的原始边界，是需要收缩扩展范围至原始边界的，所以我们求扩展边界可以这样求：
2. 下标的映射关系：在学二维前缀和模板的时候，为了在预处理二维前缀和数组 dp 时，避免处理一些边界情况，方便初始化，我们是建立的矩阵是从 dp[1][1]~dp[m][n] 计数的，但是这道题是 dp[0][0]~dp[m-1][n-1] 计数的。为了方便我们初始化，避免过度地把精力花在初始化问题和处理边界情况上，我们必须对 dp 数组多加一行，多加一列： 多加一行一列之和，我们是先根据 mat 来填 dp 表，再通过 dp 表填 answer，所以，在给 dp 表加上一行一列后，就会出现 mat 和 dp 的下标映射关系问题： 我们在求 dp[i][j] 时，在调整后，就变成找 mat[i-1][j-1] 对应的矩阵和，因此，我们的递推公式也会发送改变： 在通过 mat 填写好 dp 表之后，我们需要通过 dp 表来填写 answer，所以 dp 与 answer 的下标映射关系为 dp[i][j] 对应 answer[i-1][j-1]。

使用前缀和数组

代码实现：

public int[][] matrixBlockSum(int[][] mat, int k) {
    int m = mat.length;
    int n = mat[0].length;
    int[][] dp = new int[m + 1][n + 1];
    
    // 构建二维前缀和
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
        }
    }
    
    int[][] ans = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int r1 = Math.max(0, i - k);
            int c1 = Math.max(0, j - k);
            int r2 = Math.min(m - 1, i + k);
            int c2 = Math.min(n - 1, j + k);
            
            // 利用前缀和计算矩形区域和
            ans[i][j] = dp[r2 + 1][c2 + 1] - dp[r1][c2 + 1] - dp[r2 + 1][c1] + dp[r1][c1];
        }
    }
    
    return ans;
}