560. 和为 K 的子数组

Difficulty
Medium
Tags
前缀和
URL
https://leetcode-cn.com/problems/subarray-sum-equals-k/
Star
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
  • 1 <= nums.length <= 2 * 104
  • 1000 <= nums[i] <= 1000
  • 107 <= k <= 107

前缀和

思想
求得前缀和时候，就相当于是求两数只差等于k的个数了。
采用前缀和的思想，在遍历数组的时候，不断的将当前值加到sum_上，
  • 然后判断 sum_ - k的值之前是否出现过。（通过字典判断，为O（1）的复杂度）
  • 然后再把sum_放到hashmap中，放到hashmap的目的是因为这样访问的时候速度快，而不用再遍历一次之前的前缀和数组。
题解
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        sum_ = 0
        count = 0
        hashmap = collections.defaultdict(int)
        hashmap[0] = 1
        for i in range(len(nums)):
            sum_ += nums[i]
            temp = sum_ - k
            count += hashmap[temp]
            hashmap[sum_] += 1

        return count