[LeetCode] 560. Subarray Sum Equals K 子数组和为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:

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<Integer, Integer> 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<int>& 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<int>& nums, int k) {
        int res = 0, sum = 0, n = nums.size();
        unordered_map<int, int> m{{0, 1}};
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            res += m[sum - k];
            ++m[sum]; 
        }
        return res;
    }
};

　　　　

All LeetCode Questions List 题目汇总