这题包含负数，直接使用滑动窗口是行不通的，但是可以使用前缀和来解决这个问题。

构造前缀和

  1. [1,2,3,4,5]
  3. // 最后构造出的前缀和数组如下：
  4. [1,3,6,10,15]
  6. 那怎么找和为k的子数组呢? 定义两个指针 i 和 j，双重循环

使用前缀和在边界上面不是有很多讲究的：

  1. j 是从i 开始的
  2. 前缀和数组长度为 len + 1 ```java class Solution { public int subarraySum(int[] nums, int k) {
     if (nums == null || nums.length == 0) return 0;
 int len = nums.length;
 int[] preSum = new int[len + 1];
 for (int i = 1; i <= len; i++) {
     preSum[i] += preSum[i - 1] + nums[i - 1];
 }

    // 双重循环
    int valid = 0;
    for (int i = 1; i <= len; i++) {
        for (int j = i; j <= len; j++) {
            // 判断区间 [i,j] 的和是否==k
            if (preSum[j] - preSum[i - 1] == k) valid++;
        }
    }

    return valid;
}

}

<a name="IkBkE"></a>
# 优化：HashMap
类似求两数和。因为我们不需要求具体哪些区间的和为目标值，因此，我们可以记录区间和以及其所对应的数量，我们只需要遍历一次数组就可以得到 `valid` 结果了。<br />算法思想是：`pre[j] - pre[i - 1] == k`， 由于 `k` 值是固定的，这就变成了两数和的问题。枚举 `pre[i]` 并统计 `pre[i - 1]` 的个数即可。<br />具体操作如下以及相关细节解释如下：

1. 初始化语句 `countMap.put(0, 1)` 非常重要，
```java
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        Map<Integer, Integer> countMap = new HashMap<>();
        countMap.put(0, 1);
        int preSum = 0, valid = 0;
        for (int num : nums) {
            preSum += num;
            if (countMap.containsKey(preSum - k)) {
                valid += countMap.get(preSum - k);
            }
            // 这里是存储 k - preSum ?
            countMap.put(preSum, countMap.getOrDefault(preSum, 0) + 1);
        }
        return valid;
    }