题目描述：

LeetCode 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:

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

题目大意：

给定整数数组nums和整数k，寻找和等于k的连续子数组的个数。

注意：

1. 数组长度为[1, 20000]
2. 数组元素范围[-1000, 1000]，整数k范围[-1e7, 1e7]

解题思路：

利用字典cnt统计前N项和出现的个数

遍历数组nums：

    在cnt中将sums的计数+1

    累加前N项和为sums

    将cnt[sums - k]累加至答案

上述过程利用分类计数原理，遍历子数组的终点，通过cnt统计起点的个数。

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

 

本文链接：http://bookshadow.com/weblog/2017/04/30/leetcode-subarray-sum-equals-k/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码