题目描述

解题思路

注意题目没有说清楚，子数组是连续的。使用滑动窗口不可取，数字可能为负数。

枚举

就是双指针，一个指针指向一个数字，另一个指针往前移动，当等于sum，计数器加一。

// 暴力枚举(注意题目要求连续的)
public int subarraySum(int[] nums, int k) {
    int count = 0;
    for (int start = 0; start < nums.length; start++) {
        int sum = 0;
        for (int end = start; end >= 0; end--) {
            sum += nums[end];
            if (sum == k) {
                count++;
            }
        }
    }
    return count;
}

前缀和 + 哈希表优化

官解的思路：🔗

我的理解：
pre[i]=pre[j - 1]+nums[i]，这个公式是代表[j，i]相差的数字为nums[i]，而本题我们需要求k的连续子数组，所以可以替换为pre[i] - pre[j-1] == k。
进一步替换就为pre[j-1] ==pre[i] - k ，所以每次到pre[i]时，需要求有多少个子数组，我们只需要知道pre[j-1]有多少次即可，可以每次遍历使用hash表记录次数。
但此时p[j-1]就是前缀和，p[i]就是所有的和，所以我们可以使用pre变量来记录每次遍历的所有和，p[j-1]记录在hash表。

注意：为什么先放一个0，因为当pre[i]==k时，也算一个数组，所以0出现一次。

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    int count = 0, pre = 0;
    // 先放入0，表示和为0已经出现了一次
    map.put(0, 1);
    for (int i = 0; i < nums.length; i++) {
        pre += nums[i];
        if (map.containsKey(pre - k)) {
            // 获取前面前缀和的次数
            count += map.get(pre - k);
        }
        map.put(pre, map.getOrDefault(pre, 0) + 1);
    }
    return count;
}