LeetCode 560. Subarray Sum Equals K

Posted on | In |
Words count in article: 187 | Reading time ≈ 1

题目

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:

1
2
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
k=sum(i,j)=sum(0,j)-sum(0,i), where sum(i,j) represents the sum of all the elements from index i to j-1.

问题转化为:

1
for each j：how many i < j satisfies sum(0,i) = sum(0,j) - k

可使用一个HashMap：

1
2
key：prefixSum value
value：number of occurence of the prefixSum value。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        res, sums = 0, 0
        d = collections.defaultdict(int)
        d[0] = 1
        for i in range(len(nums)):
            sums += nums[i]
            if sums - k in d:
                res += d[sums-k]
            d[sums] += 1
        return res