【优先算法】思还故里闾，欲归道无因 - 前缀和

1. 和为K的子数组

题目链接: 560. 和为 K 的子数组

题目描述:

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2 输出：2 示例 2：

输入：nums = [1,2,3], k = 3 输出：2

解法一: 暴力解法

定义计数变量count, 两层循环遍历数组, 每次 j 从 i 的位置开始, 找到满足 [ i , j ] 区间元素和等于k时,count++. 时间复杂度为O(N^2)

解法二: 前缀和 + 哈希表

1. 问题转换并分析

①是 以 i 位置为结尾的子数组,且①满足数组元素为 k. 由此图便可将问题转化为: 当遍历数组到 i 位置时, [ 0 , i-1 ]区间中前缀和为sum[i] - k的个数.

这个时候不要直接去求前缀和数组, 然后遍历找满足条件的前缀和. 如果这么做那时间复杂度还是O(N^2)并且空间复杂度还是O(N), 并不见得比暴力解法要好. 要找前缀和并且其满足sum[i] - k, 可以利用哈希表来找, 哈希表本身就是用来查找的. 哈希表: <前缀和,出现次数>

2. 算法思路

设 i 为数组中的任意位置，用 sum[i] 表示 [0, i] 区间内所有元素的和。 想知道有多少个「以 i 为结尾的和为 k 的子数组」，就要找到有多少个起始位置为 x1, x2, x3… 使得 [x, i] 区间内的所有元素的和为 k 。那么 [0, x] 区间内的和是不是就是 sum[i] - k 了。于是问题就变成： ◦ 找到在 [0, i - 1] 区间内，有多少前缀和等于 sum[i] - k 的即可。

3. 处理细节

1. 我们不用真的初始化一个前缀和数组，因为我们只关心在 i 位置之前，有多少个前缀和等于sum[i] - k 。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边存下之前每⼀种前缀和出现的次数。 不要把前缀和都求出来后再加入哈希表, 原本应该是[ 0 , i-1 ] 的前缀和,但求完一并加入 会 使 [ i , n-1] 的前缀和也加进来, 假设[ i , n-1 ] 也有满足条件的前缀和, 就会多算.

2. 如果整个数组和为 k , 那么此时并不存在一个区间让我去找 前缀和 = sum[i] - k, 但是sum[i] = k 这个情况确实存在, 所以在我开始遍历数组之前, 应该先map.put(0,1), sum[i] - k = 0时, 次数赋为1.

4. 代码实现

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        //将前缀和为0的初始次数设置为1, 因为 k 有可能等于nums数组中某个元素的值.
        map.put(0,1);
        
        int sum = 0,ret = 0;
        for(int x : nums) {
            sum += x;//计算当前位置的前缀和.
            ret += map.getOrDefault(sum-k,0);//统计结果.
            map.put(sum,map.getOrDefault(sum,0)+1);//将当前位置的前缀和sum加入哈希表.
        }
        return ret;
    }
}

2. 和可被 K 整除的⼦数组(蓝桥杯真题)

题目链接: 974. 和可被 K 整除的⼦数组

题目描述:

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。

子数组 是数组中 连续 的部分。

示例 1：

输入：nums = [4,5,0,-2,-3,1], k = 5 输出：7 解释： 有 7 个子数组满足其元素之和可被 k = 5 整除： [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3] 示例 2:

输入: nums = [5], k = 9 输出: 0

解法一: 暴力枚举

做法与上题基本一致, 就是枚举出所有子数组的和, 时间复杂度为O(N^2).

解法二: 前缀和 + 哈希表

第一点 必要前置知识:

1. 同余定理 如果(a - b) % p = 0 , 那么 a % p = b % p . 即 如果两个数相减的差能被 p 整除，那么这两个数对 p 取模的结果相同. 例如: (7 - 4) % 3 = 0, 7 % 3 = 1, 4 % 3 = 1;

根据同余定理就可以把问题转换成, 在[0 , i-1]区间中找到满足 前缀和 % k 等于 sum[i] % k 的 所有前缀和. (这也是本题的核心.)

2. 负数取模

C++和Java中, 负数 % 正数 结果为 负数, 为了防止 重复算,统一将结果化为正数. 比如 -1 % 3 = -1 换成 (-1 % 3 + 3) % 3 = 2 . 即 a % p -> (a % p + p) % p .

第二: 具体步骤(与上题无异, 不同的是,此题中map第一个位置放的时前缀和 % k 的值. 并且确保是正数.)

设 i 为数组中的任意位置，⽤ sum[i] 表示 [0, i] 区间内所有元素的和。 • 想知道有多少个「以 i 为结尾的可被 k 整除的子数组」，就要找到有多少个起始位置为 x1, x2, x3… 使得 [x, i] 区间内的所有元素的和可被 k 整除。 • 设 [0, x ] (x < i)区间内所有元素之和等于 a ， [0, i] 区间内所有元素的和等于 b ，可得 (b - a) % k == 0 。 • 由同余定理可得， [0, x ] 区间与 [0, i] 区间内的前缀和同余。于是问题就变成： ◦ 找到在 [0, i - 1] 区间内，有多少前缀和的余数等于 sum[i] % k 的即可。 我们不用真的初始化⼀个前缀和数组，因为我们只关心在 i 位置之前，有多少个前缀和等于sum[i] - k 。因此，我们仅需用一个哈希表，一边求当前位置的前缀和，一边存下之前每⼀种前缀和出现的次数。

第三 代码实现

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
        map.put(0,1);//还是一样的,[0,i] 当sum = k时,不存在区间,但sum[i] = k存在.
        int sum = 0,ret = 0;
        for(int x : nums) {
            sum += x;//当前位置的前缀和
            int tmp = (sum % k + k) % k;//前缀和模k 的余数,原本是sum % k, 但是Java和C++存在负数模正数等于负数的问题,一并化成正数.
            ret += map.getOrDefault(tmp,0);
            map.put(tmp,map.getOrDefault(tmp,0)+1);
        }
        return ret;
    }
}

3. 连续数组

题目链接: 525. 连续数组

题目描述:

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

输入: nums = [0,1] 输出: 2 说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。 示例 2:

输入: nums = [0,1,0] 输出: 2 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

1. 暴力枚举

枚举出所有子数组, 检查子数组是否满足要求,时间复杂度为O(N^2).

2. 前缀和 + 哈希表

第一 问题分析与转换 原数组中的元素只有0和1, 题目要求的是 0 和 1 个数相等的最长子数组, 将所有的 0 换成 -1, 问题就转换成 求 和为0的最长子数组的长度.

第二 处理细节

1. 哈希表<In,In>的两个位置分别存放 [ 0 , i ]前缀和 与 位置 i .

2. 当区间[ 0 , i ]的sum[i] = 0时, 0 < j < i,不存在[0 , j] 区间. 默认一个前缀和为0的情况, 只能以 -1 为结束位置.

3. 如果有重复的sum[ i ] , 保留前面先算出来的 <sum ,i>, 舍弃后面的, 因为先算出来的更靠左边, 离 i 的距离更大, 本题要求的就是最大长度.

第三 步骤

设 i 为数组中的任意位置，⽤ sum[i] 表⽰ [0, i] 区间内所有元素的和。 想知道最⼤的「以 i 为结尾的和为 0 的⼦数组」，就要找到从左往右第⼀个 x1 使得 [x1, i]区间内的所有元素的和为 0 。那么 [0, x1 - 1] 区间内的和是不是就是 sum[i] 了。于是问题 就变成： • 找到在 [0, i - 1] 区间内，第⼀次出现 sum[i] 的位置即可。 我们不⽤真的初始化⼀个前缀和数组，因为我们只关⼼在 i 位置之前，第⼀个前缀和等于 sum[i]的位置。因此，我们仅需⽤⼀个哈希表，⼀边求当前位置的前缀和，⼀边记录第⼀次出现该前缀和的 位置。

第四 代码实现

class Solution {
    public int findMaxLength(int[] nums) {
       Map<Integer,Integer> hash = new HashMap<>();
       hash.put(0,-1); //当[0,i]sum = 0时,默认存在一个前缀和为0的情况.并且以-1为结束位置.

       int sum = 0,ret = 0;
       for(int i = 0;i < nums.length;++i) {
        if(nums[i] == 0) {
            sum += -1; //将数组中所有的 0 替换成 -1.
        }else {
            sum += nums[i];//求出当前位置的前缀和
        }
        if(hash.containsKey(sum-0)) {
            ret = Math.max(ret,i - hash.get(sum));

        }else{//有重复的只保留前面的那一对<sum,i>.  
            hash.put(sum,i);
        }
       }
       return ret;
    }
}

4. 矩阵区域和

题目链接: 1314. 矩阵区域和

题目描述:

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：

i - k <= r <= i + k, j - k <= c <= j + k 且 (r, c) 在矩阵内。

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1 输出：[[12,21,16],[27,45,33],[24,39,28]] 示例 2：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2 输出：[[45,45,45],[45,45,45],[45,45,45]]

提示：

m == mat.length n == mat[i].length 1 <= m, n, k <= 100 1 <= mat[i][j] <= 100