560. 和为 K 的子数组 (opens new window)

1.前缀和+哈希

解题思路：使用哈希表记录前缀和，key为前缀和的值，value为该前缀和出现的次数，非常吊的思路，适用于处理连续子数组的另一种思路，

能够使用前缀和思路，关键在于数组上所有连续子数组都可以表示为两个前缀和相减。这里在哈希中map.put(0,1)的原因是考虑到前缀和本身也可以直接等于k，相当于前缀和本身也可以看作是一个前缀和(自身)减去另一个前缀和(0)。

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

2.暴力

class Solution {
    public int subarraySum(int[] nums, int k) {
        int sum;
        int ans=0;
        for(int i=0;i<nums.length;i++){
            sum=0;
            for(int j=i;j<nums.length;j++){
                sum+=nums[j];
                if(sum==k) ans++;
            }
        }
        return ans;

    }
}