和为K的子数组

题目

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subarray-sum-equals-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

一开始想到的是使用窗口滑动,但是因为有负数存在,则没办法判断窗口应该向哪边滑动.

所以使用前缀和的方式来解决.先计算出数组中所有的前缀和,然后用后面的前缀和减去前面的前缀和及是符合条件的子数组.

上面的还是O(n2)的时间复杂度,优化的话可以选择边计算前缀和,边在hash中获取当前符合条件的前缀和的前缀和个数.

代码

单是前缀和
class Solution {
    public int subarraySum(int[] nums, int k) {
        int length = nums.length;
        int[] preSum = new int[length+1];
        preSum[0] = 0;
        for (int i = 0; i < length; i++) {
            preSum[i+1] = preSum[i] + nums[i];
        }

        int count = 0;
        for(int left = 0;left < length;left++){
            for(int right = left;right < length;right++){
                if (preSum[right+1] -preSum[left] == k){
                    count++;
                }
            }
        }
        return count;
    }
}

使用hash

public class Solution {

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