题目

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 2 * 10⁴
• -1000 <= nums[i] <= 1000
• -10⁷ <= k <= 10⁷

解法

解法一 前缀和数组 + 哈希（两数之和）

前缀和数组：子数组 [i, j] 元素的总和 可以用 [0, j] – [0, i] 来计算得到；

哈希优化：参照两数之和的思想，设计一个哈希表，key为 [0, i] 前缀和的值，value为这个前缀和对应的 i 可能的个数；

用一个循环实现：

1. 构建前缀和数组及次数哈希表
2. 遍历 nums 数组，查找 preSums[j] – k 的前缀和的次数 （以 j 为终点找符合要求的子数组头部i的个数），因为边构建次数哈希表边进行查找，可以保证不会查询到以j为起点后面的次数，也就是不会重复。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int cnt = 0;
        int[] preSums = new int[nums.length];
        Map<Integer, Integer> map = new HashMap<>();
        // 1 构建前缀和次数Map
        for (int i = 0; i < nums.length; i++) {
            preSums[i] = i==0 ? nums[i] : preSums[i - 1] + nums[i];
            
            // 在构建次数Map之前计算次数，可以保证不会找到自身和后面符合条件的次数。
            if (k == preSums[i]) {
                cnt++;
            }
            if (map.containsKey(preSums[i] - k)) {
                    cnt += map.get(preSums[i] - k);
            }

            // 构建次数Map
            if (!map.containsKey(preSums[i])) {
                map.put(preSums[i], 1);
                continue;
            }
            map.put(preSums[i], map.get(preSums[i]) + 1);
        }
        return cnt;
    }
}

时间复杂度 O(N²)

优化

实际上，不需要实际构建前缀和preSums数组，只要用preSum来保存这一次的前缀和即可。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int cnt = 0;
        int preSum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        // 1 构建前缀和次数Map
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            preSum += nums[i];
            
            // 在构建次数Map之前计算次数，可以保证不会找到自身和后面符合条件的次数。
            if (map.containsKey(preSum - k)) {
                    cnt += map.get(preSum - k);
            }

            // 构建次数Map
            if (!map.containsKey(preSum)) {
                map.put(preSum, 1);
                continue;
            }
            map.put(preSum, map.get(preSum) + 1);
        }
        return cnt;
    }
}

确实得到了小幅度的优化。

小结

• 计算连续子串的和 ——> 前缀和的思想！

sum[i, j] = preSum[0, j] - preSum[0, i]

• “两数之和“的思想：要找组成目标和的元素，可以遍历一次数组，用一个元素计算出另一个元素。可以设计一个哈希表，在这个哈希表里面十分高效地查找出来该元素的位置（两数之和）或者出现次数（本题），需要什么就在这个哈希表的value里存什么。