560. Subarray-Sum-Equals-K

difficulty: Medium

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Constraints:

• The length of the array is in range [1, 20,000].

• The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Method One

class Solution {
    public int subarraySum(int[] nums, int k) {
        /*
        以下面的为例啊
        index  0 1 2  3  4  5  6  7
        value  3 4 7  2  -3 1  4  2 
        preSum 3 7 14 16 13 14 18 20
        如果 preSum[i] - preSum[j] == 0, 说明 i j 之间的和是 0，
        如果 preSum[i] - preSum[j] == k, 说明 i j 之间的和是 k.
        因此，对于 preSum[i] - k == preSum[j], 如果能找到 preSum[j], 就可以符合。
        这就是 Two Sum! 这个题和 Two Sum 竟然一样。
        当然了，这个题不能用Set, 因为 Two Sum 没有重复的，只有唯一解，但是这个题，
        很可能出现重复的 preSum。
        例如，
        
        [0,0,0,0,0,0,0,0,0,0]
        0
        */
        
        if(nums.length < 1) return 0;
        Map<Integer, Integer> preSums = new HashMap<>();
        preSums.put(0, 1);
        int curSum = 0;
        int count = 0;
        for(int i = 0; i < nums.length; i++) {
            curSum += nums[i];
            int target = curSum - k;
            if(preSums.containsKey(target)){
                count += preSums.get(target);
            }
            preSums.put(curSum, preSums.getOrDefault(curSum, 0) + 1);
        }
        return count;
    }
}
        */
​

这个题可能会想用 sliding window, 但是因为有负元素的存在，sliding window是失效的。 具体更严谨的解释我也还没想，但是这是一个很直觉的思路。

// 写于2023
class Solution {
    public int subarraySum(int[] nums, int k) {
        int[] prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        int count = 0;
        Map<Integer, Integer> prefixCount = new HashMap<>();
        for (int right = 0; right < prefix.length; right++) {
            count += prefixCount.getOrDefault(prefix[right] - k, 0);
            prefixCount.put(prefix[right], prefixCount.getOrDefault(prefix[right], 0) + 1);
        }
        return count;
    }
}