前缀和

Leetcode560.和为k的子数组

1. 思路

我们可以基于方法一利用数据结构进行进一步的优化，我们知道方法一的瓶颈在于对每个 i，我们需要枚举所有的 j来判断是否符合条件，这一步是否可以优化呢？答案是可以的。
我们定义 为 里所有数的和，则 可以由 递推而来，即：

那么[j..i] 这个子数组和为 k这个条件我们可以转化为
pre[i]=pre[i−1]+nums[i]
简单移项可得符合条件的下标 j需要满足
pre[j−1]==pre[i]−k
所以我们考虑以 ii 结尾的和为 kk 的连续子数组个数时只要统计有多少个前缀和为 \textit{pre}[i]-kpre[i]−k 的 \textit{pre}[j]pre[j] 即可。我们建立哈希表 \textit{mp}mp，以和为键，出现次数为对应的值，记录 \textit{pre}[i]pre[i] 出现的次数，从左往右边更新 \textit{mp}mp 边计算答案，那么以 ii 结尾的答案 \textit{mp}[\textit{pre}[i]-k]mp[pre[i]−k] 即可在 O(1)O(1) 时间内得到。最后的答案即为所有下标结尾的和为 kk 的子数组个数之和。

需要注意的是，从左往右边更新边计算的时候已经保证了\textit{mp}[\textit{pre}[i]-k]mp[pre[i]−k] 里记录的pre[j] 的下标范围是0≤j≤i 。同时，由于pre[i] 的计算只与前一项的答案有关，因此我们可以不用建立 pre 数组，直接用pre 变量来记录pre[i−1] 的答案即可。

public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        int[] suffix = new int[n+1];
        for(int i=1;i<suffix.length;i++){
            suffix[i] = suffix[i-1]+nums[i-1];
        }
        int ans = 0;
        hashMap.put(0,1);
        for(int i=1;i<suffix.length;i++){
           if(hashMap.get(suffix[i]-k)!=null){
                ans+=hashMap.get(suffix[i]-k);
            }
            hashMap.put(suffix[i],hashMap.getOrDefault(suffix[i],0)+1);
        }
        return ans;
  }