前缀和模板

S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

         // 计算前缀和数组
         for(int i=0; i<nums.length; i++)
             preSum[i+1] = preSum[i] + nums[i];

1. 和为K的子数组

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

class Solution {
    // 1. 暴力枚举
    // public int subarraySum(int[] nums, int k) {
    //     int res = 0;
    //     if(nums == null || nums.length == 0)
    //         return res;
    //     for(int i=0; i<nums.length; i++){
    //         int sum = 0;
    //         for(int j=i; j>=0; j--){
    //             sum += nums[j];
    //             if(sum == k)
    //                 res++;
    //         }
    //     }
    //     return res;
    // }

    // 2. 前缀和
    // public int subarraySum(int[] nums, int k) {
    //     int res = 0;
    //     if(nums == null || nums.length == 0)
    //         return res;
    //     int[] preSum = new int[nums.length+1];
    //     // 计算前缀和数组
    //     for(int i=0; i<nums.length; i++)
    //         preSum[i+1] = preSum[i] + nums[i];

    //     for(int i=0; i<nums.length; i++){
    //         for(int j=i; j>=0; j--){
    //             if(preSum[i+1] - preSum[j] == k)
    //                 res++;
    //         }
    //     }
    //     return res;
    // }

    // 3. 前缀和+Hash表
    public int subarraySum(int[] nums, int k) {
        int res = 0, pre = 0;
        if(nums == null || nums.length == 0)
            return res;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // 表示前缀和为0，个数为1
        for(int i=0; i<nums.length; i++){
            pre = pre + nums[i];
            if(map.containsKey(pre - k)){
                res += map.get(pre - k);
            }
            map.put(pre, map.getOrDefault(pre, 0)+1);
        }
        return res;
    }
}

2. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        if(nums == null || nums.length == 0)
            return new int[0];
        int pre = 0;
        int[] res = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<nums.length; i++){
            if(map.containsKey(target - nums[i])){
                res[0] = map.get(target - nums[i]);
                res[1] = i;
                break;
            }
            map.put(nums[i], i);
        }
        return res;
    }
}

3. 统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。

class Solution {
    // 前缀和+hash表
    public int numberOfSubarrays(int[] nums, int k) {
        if(nums == null || nums.length == 0)    
            return 0;
        // 数组preSum的下标是前缀和（即当前奇数的个数），值是前缀和的个数
        int[] preSum = new int[nums.length+1]; // 用数组表示Hash表
        // 遍历原数组，计算当前的前缀和，统计到prefixCnt数组中，并且在res中累加上与当前前缀和差值为k的前缀和的个数
        int sum = 0, res = 0;
        preSum[0] = 1; // 表示奇数为0的个数
        for(int i=0; i<nums.length; i++){
            sum += nums[i] & 1;
            preSum[sum]++;
            if(sum >= k){
                res += preSum[sum-k];
            }
        }
        return res;
    }
}

4. 四数相加 II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解释:两个元组如下:
1.(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2.(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

class Solution {
    // 分组+Hash表
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> mapAB = new HashMap<>();
        int res = 0;
        // nums1, nums2一组
        for(int i=0; i<nums1.length; i++){
            for(int j=0; j<nums2.length; j++){
                int tmp = nums1[i]+nums2[j];
                mapAB.put(tmp, mapAB.getOrDefault(tmp, 0) + 1);
            }
        }

        // nums3, nums4一组
        for(int i=0; i<nums3.length; i++){
            for(int j=0; j<nums4.length; j++){
                int tmp = nums3[i]+nums4[j];
                if(mapAB.containsKey(-tmp)){
                    res += mapAB.get(-tmp);
                }
            }
        }
        return res;
    }
}

5.和至少为 K 的最短子数组

返回 A 的最短的非空连续子数组的长度，该子数组的和至少为 K 。
如果没有和至少为 K 的非空子数组，返回 -1 。

输入：A = [1], K = 1
输出：1

class Solution {
    // 前缀和 + 变种单调栈结构（栈底到栈顶单调递增）
    public int shortestSubarray(int[] nums, int k) {
        int[] sum = new int[nums.length+1]; // 前缀和数组
        for(int i=0; i<nums.length; i++){
            sum[i+1] = sum[i] + nums[i];
        }
        int res = -1;
        Deque<Integer> stack = new LinkedList<>();
        for(int i=0; i<=nums.length; i++){
            while(!stack.isEmpty() && sum[i] < sum[stack.peekLast()]){
                stack.removeLast();
            }
            while(!stack.isEmpty()){
                if(sum[i] - sum[stack.peekFirst()] >= k){
                    res = res == -1 ? i-stack.peekFirst() : Math.min(res,i-stack.peekFirst());
                    stack.removeFirst();
                }else{
                    break;
                }
            }
            if(sum[i] >= k){
                res = res==-1?i+1:Math.min(res,i+1);
            }
            stack.addLast(i);
        }
        return res;
    }
}

6.连续数组

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

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

思路：
由于「00 和 11 的数量相同」等价于「11 的数量减去 00 的数量等于 00」，我们可以将数组中的 00 视作 -1−1，则原问题转换成「求最长的连续子数组，其元素和为 00」。

class Solution {
    // 前缀和+hash
    public int findMaxLength(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int cur = 0, ans = 0;
        for(int i=0; i<nums.length; i++){
            if(nums[i] == 0){
                cur += -1;
            }else{
                cur += 1;
            }
            if(map.containsKey(cur)){
                ans = Math.max(ans, i-map.get(cur));
            }else{
                map.put(cur, i);
            }
        }
        return ans;
    }
}

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

思路：
通常，涉及连续子数组问题的时候，我们使用前缀和来解决。

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> record = new HashMap<Integer, Integer>();
        record.put(0, 1);
        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;
    }
}