560.和为K的子数组 · 陈小达的博客

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

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

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

这道题分析一下，因为数组里面有负数的存在，那就不能保证向右扩展的时候是递增的，也就不可以使用滑动窗口，所以只能使用前缀和数组，来获得字串，所以写了一个O(n^2)的算法

/* public static int subarraySum(int[] arr, int k) {
     //因为是有负数的情况，就不可以使用滑动窗口，得使用前缀和
     //在生成前缀和数组的时候，尝试一下有没有区间满足k值
     int ans = 0;
     int[] pre = new int[arr.length];
     pre[0] = arr[0];
     if (arr[0] == k) {
         ans++;
     }
     for (int i = 1; i < arr.length; i++) {

         pre[i] = pre[i - 1] + arr[i];
         if (pre[i] == k) {
             ans++;
         }
         for (int j = 0; j < i; j++) {
             if (pre[i] - pre[j] == k) {
                 ans++;
             }
         }
     }
     return ans;
 }*/

但是如何优化呢？

看了题解发现可以使用哈希表来记录之前的前缀答案，从而只需要遍历一遍数组就可以实现答案的记录

也就是说，我需要记录之前的前缀和数字出现的频率，然后设我期望的前缀和数字为x，那么就有arr[i]-x=k

所以x=arr[i]-k,也就是说只要每次遍历的时候找到之前的x，再将答案加上hashMap记录x的频率，就可以直接加在答案上

public int subarraySum(int[] nums, int k) {
    int ans = 0;
    int sum = 0;
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    for (int num : nums) {
        sum += num;
        if(map.containsKey(sum - k)){
            ans = ans + map.get(sum - k);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    return ans;
}