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 = 2Output: 2

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

解法1: Brute force. 用两丛循环i, j，计算sum[i, j]，如果等于K则记录结果。T: O(n^2)  S: O(1),  会TLE

解法2：Hashtable，基于公式 sum(i - j) = sum(0, j) - sum(0, i), 每循环一次都把数字累加到sum, 并用一个哈希表记录，key是sum， value是出现过的次数。当满足sum - K在哈希表中时，说明去掉之前那段和的数后剩下的数字和等于K, 满足条件，把记录的次数累加到结果(因为有多种组合可能)。T: O(n), S: O(n).

参考: https://discuss.leetcode.com/topic/87850/java-solution-presum-hashmap

Java:

public class _560 {    public int subarraySum(int[] nums, int k) {        Map
     
       preSum = new HashMap();        int sum = 0;        int result = 0;        preSum.put(0, 1);        for (int i = 0; i < nums.length; i++) {            sum += nums[i];            if (preSum.containsKey(sum - k)) {                result += preSum.get(sum - k);            }            preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);        }        return result;    }}　
     

Python:

class Solution(object):    def subarraySum(self, nums, k):        """        :type nums: List[int]        :type k: int        :rtype: int        """        ans = sums = 0        cnt = collections.Counter()        for num in nums:            cnt[sums] += 1            sums += num            ans += cnt[sums - k]        return ans　

Python:

def subarraySum(self, nums, k):        count, cur, res = {0: 1}, 0, 0        for v in nums:            cur += v            res += count.get(cur - k, 0)            count[cur] = count.get(cur, 0) + 1        return res　　

Python: wo

class Solution(object):    def subarraySum(self, nums, k):        """        :type nums: List[int]        :type k: int        :rtype: int        """        return res                res, sums = 0, 0        lookup = collections.Counter()        lookup[0] = 1 # important        for num in nums:            sums += num            if lookup[sums - k] > 0:                res += lookup[sums - k]            lookup[sums] += 1                    return res        　

Python: TLE

class Solution(object):    def subarraySum(self, nums, k):        """        :type nums: List[int]        :type k: int        :rtype: int        """        res = 0        for i in xrange(len(nums)):            sum = 0            for j in xrange(i, len(nums)):                sum += nums[j]                   if sum == k:                    res += 1                        return res  　

C++:

class Solution {public:    int subarraySum(vector
     
      & nums, int k) {        int res = 0, n = nums.size();        for (int i = 0; i < n; ++i) {            int sum = nums[i];            if (sum == k) ++res;            for (int j = i + 1; j < n; ++j) {                sum += nums[j];                if (sum == k) ++res;            }        }        return res;    }};
     

C++:

class Solution {public:    int subarraySum(vector
     
      & nums, int k) {        int res = 0, sum = 0, n = nums.size();        unordered_map
      
        m{
    {0, 1}};        for (int i = 0; i < n; ++i) {            sum += nums[i];            res += m[sum - k];            ++m[sum];         }        return res;    }};