leetcode 560 和为K的连续子数组

在一个数组中，找到和为K的连续子数组的个数。

可以很自然的想到枚举所有子数组组合。复杂度为n^2

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

可以利用前缀和优化计算。preSum(i)为前i个数的和。sum(i,j)==k ====> preSum(j)-preSum(i-1)==k

我们简单的移项可以得到   preSum(j)-k == preSum(i-1)

我们利用哈希表存储preSum的值和它的个数。 统计 PreSum(j)-k 存在的总个数就可以了。

要注意的是，PreSum=0，天生就存个1个。

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