利用前缀和求解的lc题目汇总

总结

前缀和是解决连续子数组的和的
要注意map的初始化条件一般为map.put(0,1)表示考虑当前元素本身作为一个子数组符合对k的相关性质的情况

题目

1 lc560. 和为 K 的子数组

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n=nums.length;
        Map<Integer,Integer>mp=new HashMap<>();
        mp.put(0,1);//需要注意的一个边界条件是，我们需要对哈希表初始化，记录 record[0]=1，这样就考虑了前缀和本身等于k的情况。
        int sum=0;
        int res=0;
        for(int num:nums){
            sum+=num;
            if(mp.containsKey(sum-k)){
                res+=mp.get(sum-k);
            }
            mp.put(sum,mp.getOrDefault(sum,0)+1);
        }
        return res;
    }
}

2 lc523. 连续的子数组和

这里有两种写法：
写法一（错误）：

public boolean checkSubarraySum(int[] nums, int k) {
        int n=nums.length;
        Map<Integer,Integer>mp=new HashMap<>();
        mp.put(0,-1);
        int s=0,res=0;
        for(int i=0;i<n;i++){
            s+=nums[i];
            int r=s%k;
            if(mp.containsKey(r)&&i-mp.get(r)>1){
                System.out.println(mp.containsKey(r)+", "+(i-mp.get(r)));
                return true;
            }
            else mp.put(r,i);
    
        }
        return false;
    }

写法二：
public boolean checkSubarraySum3(int[] nums, int k) {
        int n=nums.length;
        Map<Integer,Integer>mp=new HashMap<>();
        mp.put(0,-1);
        int s=0;
        for(int i=0;i<n;i++){
            s+=nums[i];
            int r=s%k;
            if(mp.containsKey(r)){
                System.out.println(mp.containsKey(r)+", "+(i-mp.get(r)));
                if(i-mp.get(r)>1){
                    return true;
                }
            }
            else mp.put(r,i);//#A
    
        }
        return false;
    }

分析：写法一与写法二看起来几乎没有区别，为什么写法一错了呢，
他们唯一的不同就在于if-else分支的写法上，我们可以看到针对同一个测试案例，写法二的输出语句多了两行，说明错误方法在碰到分支时多走了两个else分支，即少走两个if分支，这就是方法一分支特点导致的bug，因为方法一的分支有两个条件，比方法二更苛刻

3 lc325. 和等于 k 的最长子数组长度

总结：这一道题目是第二题lc523的变形题，但是这里有一个区别就“ 确保记录的是第一次出现的位置”上的判断,之所以不同是因为字典里key不同，lc523的key存储的是模值，而这道题存储的是前缀和

public int maxSubArrayLen2(int[] nums, int k) {
    int n = nums.length;
    // 哈希表，映射前缀和值到第一次出现的下标位置
    Map<Integer, Integer> preSumIndex = new HashMap<>();
    int ans = 0;
    // 前缀和
    int preSum = 0;
    // 0 出现的位置在 -1 位置处
    preSumIndex.put(0, -1);
    for (int i = 0; i < n; ++i) {
        // 累加前缀和
        preSum += nums[i];
        // 确保记录的是第一次出现的位置
        if (!preSumIndex.containsKey(preSum)) {//#A
            preSumIndex.put(preSum, i);
        }
        // 检查一下是否需要更新答案
        if (preSumIndex.containsKey(preSum - k)) {
            ans = Math.max(ans, i - preSumIndex.get(preSum - k));
        }
    }
    return ans;
}

4 lc930. 和相同的二元子数组

这道题和第三题类似，都是"和等于k"系列，只不过这里求方案数，而lc325求最值

class Solution {
    public int numSubarraysWithSum(int[] nums, int k) {
        int n=nums.length;
        Map<Integer,Integer>mp=new HashMap<>();
        mp.put(0,1);
        int s=0,res=0;
        for(int i=0;i<n;i++){
            s+=nums[i];
            int diff=s-k;
            int same=mp.getOrDefault(diff,0);
            if(mp.containsKey(diff)){
                res+=same;
            }
            mp.put(s,mp.getOrDefault(s,0)+1);
        }
        return res;
    }
}

5 lc974. 和可被 K 整除的子数组(lc523的扩展，求方案数)

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> record = new HashMap<Integer, Integer>();
        record.put(0, 1);//需要注意的一个边界条件是，我们需要对哈希表初始化，记录 record[0]=1，这样就考虑了前缀和本身被 k 整除的情况。
        int sum = 0, ans = 0;
        for (int elem : nums) {
            sum += elem;
            // 注意 Java 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
            int modulus = (sum % k + k) % k;
            int same = record.getOrDefault(modulus, 0);
            ans += same;
            record.put(modulus, same + 1);
        }
        return ans;
    }
}


作者：力扣官方题解
链接：https://leetcode.cn/problems/subarray-sums-divisible-by-k/solutions/187947/he-ke-bei-k-zheng-chu-de-zi-shu-zu-by-leetcode-sol/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

6 lc1524. 和为奇数的子数组数目
方法一：利用第5题，一个子数组的和要么为偶数，要么为奇数，所以我们将这道题转化为求和能被2整除的子数组方案数，然后再用排列组合求出总方案数，再用total-偶数的方案数即为答案

class Solution {
    long mod=(long)1e9+7;
    public int numOfSubarrays(int[] arr) {
        int n=arr.length;
        int s=0;
        long res=0;
        Map<Integer,Integer>mp=new HashMap<>();
        mp.put(0,1);
        for(int num:arr){
            s+=num;
            int r=s%2;
            int same=mp.getOrDefault(r,0);
            res+=same;
            mp.put(r,same+1);
            
        }
        long total=(long)(1+n)*n/2;
        return (int)((total-res)%mod);
    }
}
方法二：方法一属于正难则反的思路解题，那么这里则属于顺着思路解题



long mod=(long)1e9+7;
    public int numOfSubarrays(int[] arr) {
        int n=arr.length;
        int s=0;
        long res=0;
        int[]mp=new int[]{1,0};
        for(int num:arr){
            s+=num;
            int r=(s+1)%2;//奇数=偶数+奇数，如果s为奇数，则sum[0,1,...j]必为偶数，所以此时需要求偶数的个数，s+1刚好为偶数，可以求出其偶数
            int same=mp[r];
            res+=same;
            mp[s%2]++;//因为s本身还是偶数前缀和，是事实上的需要放入map中的结果
        }
        return (int)(res%mod);
    }
方法三（没弄懂，待定）：



class Solution {
    public int numOfSubarrays(int[] arr) {
        final int MODULO = 1000000007;
        int odd = 0, even = 1;
        int subarrays = 0;
        int sum = 0;
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            sum += arr[i];
            subarrays = (subarrays + (sum % 2 == 0 ? odd : even)) % MODULO;// 奇数+奇数=偶数，偶数+偶数=偶数，但是这里只讨论了第一种，第二种呢？
            if (sum % 2 == 0) {
                even++;
            } else {
                odd++;
            }
        }
        return subarrays;
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/number-of-sub-arrays-with-odd-sum/solutions/357914/he-wei-qi-shu-de-zi-shu-zu-shu-mu-by-leetcode-solu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。