[LeetCode]Subarray Sum Equals K

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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