优选算法的睿智之林：前缀和专题(二)

专栏：算法的魔法世界

个人主页：手握风云

一、例题讲解

1.1. 和为 K 的子数组

        我们先来思考暴力枚举：利用双指针left和right，当right移动到某一个位置时，left与right构成的区间之和为k时，此时right不能停止，数组元素可能为负的，有可能后面还存在和为k的子数组。明显时间复杂度为。

        分析到这里，我们会发现，这里是不能用滑动窗口来做优化。因为滑动窗口采用的双指针是具有单调性的。如果出现了下图这种情况，两端区间之和为0，而right是不能回退的，就会漏掉这种情况。

        和为k的子数组，相当于也是求某段区间的和，我们来思考一下前缀和算法。我们先来引入一个概念：以i为结尾的子数组。我i们固定一个下标为结尾，向前枚举子数组，再去统计和为k的子数组，但这样时间复杂度并没有得到优化。根据下图，那我们就可以转化成多少个前缀和为sum-k的子数组。但我们不能上来就预处理出前缀和数组，因为前缀和处理时间复杂度为，还有查找的时间复杂度，反而不如暴力枚举。

        那我们再引入一个哈希表来来记录前缀和出现的次数，这样就不用再创建前缀和数组，直接在哈希表中快速寻找。我们还有一些细节需要思考：1.哈希表加入的时机。先来想一下算完所有的前缀和再丢进哈希表中行不行？前面我们分析到需要i位置之前的区间，如果全丢进哈希表中，就会统计出i位置之后的。所以哈希表只保存[0,i-1]区间的前缀和。2.我们不用真的去创建一个哈希表，只需要用用一个sum来标记i前一个位置的前缀和。3.如果整个前缀和都为k？

        完整代码：

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1);
        
        int sum = 0,ret = 0;
        for (int x = 0; x < nums.length; x++) {
            sum += nums[x];//记录当前位置的前缀和
            ret += map.getOrDefault(sum - k,0);//统计结果
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return ret;
    }
}

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

        这道题与上一题大同小异，暴力解法的思路也与上面大差不差。

        再讲第二种解法之前，我们需要先引入两个知识点：1.同余定理。(a - b) / p = k，a % p = b % p。如果两个数的差能被p整除，那么两个数模p的余数相等。2.C++与Java中负数%正数的结果以及修正。因为负数%正数是一个负数，再加上这个正数即为正确结果。a%p+p，正数%正数直接得到正确结果，为了正负统一，(a%p+p)%p。

        下面我们就可以利用上面一题的前缀和与哈希表。根据上面的两个知识点，我们只需要在[0,i-1]区间内找到有多少个前缀和余数等于(sum%k + k)%k。

        完整代码实现：

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0 % k, 1);

        int sum = 0, ret = 0;
        for (int x : nums) {
            sum += x;
            int r = (sum % k + k) % k;
            ret += hash.getOrDefault(r, 0);//统计结果
            hash.put(r, hash.getOrDefault(r, 0) + 1);
        }
        return ret;
    }
}

1.3. 连续数组

        如果说我们直接去统计0和1的个数，可能有些困难。但如果我们把0变成-1，就可以转化成和为0的子数组，此时这道题的算法原理与第一题是一样的。但这道题的细节却与第一题却有很多不一样的。1.哈希表里面存什么。我们需要求的是最长的子数组，所以哈希表里面要存前缀和和下标才能计算后面的长度。2.如果有重复的<sum,i>，我们肯定是存越靠左的下标。3.默认的前缀和为0的时候，hash[0] = -1。4.长度的计算。实际计算的时候不包含j这个点，len = i - j + 1 - 1。

        完整代码：

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0,-1);

        int sum = 0,ret = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += (nums[i] == 0 ? -1 : 1);//计算当前位置的前缀和
            if(hash.containsKey(sum)) ret = Math.max(ret,i-hash.get(sum));
            else hash.put(sum,i);
        }
        return ret;
    }
}

1.4. 矩阵区域和

        题目有一些难理解，我们直接画图：我们以示例1为例，以mat[0][0]为中心，上下左右各扩展一个方格组成的正方形，求这个正方形的区域和。

        我们先来回顾一下二位前缀和的计算：dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i][j]。ret = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]。

        重点来了：我们想求answer[i][j]的时候，我们得知道在mat矩阵中所表示的区域。我们利用建系的思想，左上角坐标为(i-k,j-k)，右下角坐标为(i+k,j+k)，如果坐标越界，就得回退到0或者矩阵的最大值。我们为了方便处理，可以写成x1=max(0,i-k)，y1=max(0,j-k)，x2=min(m-1,i+k)，y2=min(n-1,j+k)。

        我们还需要处理下标的映射关系：我们在二维前缀和模板里面，矩阵的下标都是从1开始计算的，但这里确实从0开始计算的。我们可以从递推公式里面进行修改。如果我们要在预处理矩阵dp[x][y]里面里的值，我们需要在mat[x-1][y-1]的位置找，在answer[x+1][y+1]的位置填入。

        完整代码实现：

public class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length, n = mat[0].length;

        //1.预处理前缀和矩阵
        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];
            }
        }

        //2.使用前缀和矩阵
        int[][] ret = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x1 = Math.max(0, i - k) + 1, y1 = Math.max(0, j - k) + 1;
                int x2 = Math.min(m - 1, i + k) + 1, y2 = Math.min(n - 1, j + k) + 1;
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ret;
    }
}