【Java 优选算法】前缀和(下) 如有错误,欢迎指出~

欢迎关注个人主页:逸狼


创造不易,可以点点赞吗~

如有错误,欢迎指出~



和为K的子数组

题目链接

解法

该题存在0 和负数,且不具备单调性,所以不可以使用双指针解决

解法1: 暴力枚举O(n^2): 从0下标开始枚举加和,判断和是否为k,且要一直遍历到数组结束,因为存在0和负数

解法2: 前缀和 + 哈希表: 

将问题转化为 : 讨论以 i 位置结尾的所有子数组 ,在[0, i - 1]区间内,有多少个前缀和等于sum[i] - k, smu[i] 表示数组在i 位置的前缀和

利用哈希表统计:<int, int> ,第一个int用于统计前缀和,第二个int用于统计其出现的次数

细节问题:

  1. 前缀和加入哈希表的时机: 在计算i 位置之前,哈希表里面只保存[0, i - 1] 位置的前缀和
  2. 不用真的创建一个前缀和数组,用一个变量sum来标记前一个位置的前缀和即可
  3. 考虑整个前缀和等于k的情况, 将hash<0, 1>提前丢入哈希表里面

画图举例

代码

class Solution {
 public int subarraySum(int[] nums, int k) {
 Map hash = new HashMap();
 hash.put(0, 1);
 int sum = 0, ret = 0;
 for(int x : nums){
 sum += x; //计算当前位置的前缀和
 ret += hash.getOrDefault(sum - k, 0);//统计结果
 hash.put(sum, hash.getOrDefault(sum, 0) + 1);//把当前的前缀和丢到哈希表里面
 }
 return ret;
 }
}

和可被K整除的子数组

题目链接

解法

补充知识: 

同余定理: 如果(a - b) ÷ p=k.....0 则a%p = b%p

因为在c++ 或java中,有 负数 % 正数 = 负数 -> 所以要修正结果(将负数修正为正数): a % p + p,为了让正负通一 ,则使用(a % p + p) % p , 即将原来a 变为a % p + p

 解法: 前缀和 + 哈希表

在[0, i - 1]区间内,找到有多少个前缀和的余数等于(sum % k + k) % k

利用哈希表统计:<int, int> ,第一个int用于统计前缀和的余数,第二个int用于统计其出现的次数

代码

class Solution {
 public int subarraysDivByK(int[] nums, int k) {
 Map 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;
 }
}

连续数组

题目链接

解法

题目给的是二进制数组只有0和1,要求找到最长的数组,该数组中的0和1的数目相等,我们可以将问题转化为: 把所有的0 修改为-1,在数组中,找出最长的子数组,使子数组中所有的元素的和为0

解法: 前缀和 + 哈希表

细节问题: 

  1. hash<int, int> hash表,第一个int存的是前缀和, 第二个int 存的是其下标
  2. 存入哈希表的时机: 使用完之后丢入哈希表
  3. 如有重复的<sum, i> ,只保留前面的那一对<sum, i>
  4. 默认的前缀和为0的情况, hash[0] = -1;
  5. 长度计算: i - j

代码

class Solution {
 public int findMaxLength(int[] nums) {
 Map hash = new HashMap();
 hash.put(0, -1);//默认存在一个前缀和为0的情况
 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;
 }
}

矩阵区域和

题目链接

解法

理解题意,要求的是数组中mat[i][j]向周围扩展k个单位的数组之和,超出数组范围的不考虑

利用二维前缀和, 先列出前缀和的公式

代码

class Solution {
 public int[][] matrixBlockSum(int[][] mat, int k) {
 int m = mat.length, n = mat[0].length;
 //预处理前缀和矩阵
 int[][] dp = new int[m + 1][n + 1];
 for(int i = 1; i 

作者:逸狼原文地址:https://blog.csdn.net/2301_80898480/article/details/145228695

%s 个评论

要回复文章请先登录注册