560. Subarray Sum Equals K

发表于 | 分类于

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

Note:

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].

解法1：O(N) Time + O(N) Space

这题和2Sum的思路有点像。首先是一道continuous sum的题，可以考虑用prefix sum的办法。
每次计算一个累加和，假设为sum，sum-presum=k也就意味着，sum-k=presum,如果我们用一个hashtable存储每一个presum出现的次数，那就可以指导对于任意一个sum，其满足要求的presum是否出现过，并且出现过几次。这一点和2sum是一样的，只是一个用加法一个用减法。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    public int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int sum = 0;
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum == k) {
                cnt++;
            }
            if (map.containsKey(sum - k)) {
                cnt += map.get(sum - k);
            }
            if (map.containsKey(sum)) {
                map.put(sum, map.get(sum) + 1);
            } else {
                map.put(sum, 1);
            }
        }
        return cnt;
    }
}