【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用于统计其出现的次数
细节问题:
- 前缀和加入哈希表的时机: 在计算i 位置之前,哈希表里面只保存[0, i - 1] 位置的前缀和
- 不用真的创建一个前缀和数组,用一个变量sum来标记前一个位置的前缀和即可
- 考虑整个前缀和等于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
解法: 前缀和 + 哈希表
细节问题:
- hash<int, int> hash表,第一个int存的是前缀和, 第二个int 存的是其下标
- 存入哈希表的时机: 使用完之后丢入哈希表
- 如有重复的<sum, i> ,只保留前面的那一对<sum, i>
- 默认的前缀和为0的情况, hash[0] = -1;
- 长度计算: 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