LeetCode 热题100-10 和为 K 的子数组

和为 K 的子数组

给你一个整数数组 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
• -10e7 <= k <= 10e7

这道题目首先想到的是暴力，从左边开始遍历i，然后再用个指针从i+1遍历->len(nums)，这样的话应该o(n²)， 可惜python通过不了（貌似java可以...

所以只好学点新东西吧。。。前缀和

用hash表来优化一下，hash表存的也是前缀和，但是可以一边计算前缀和一边存hash

找pre_sum-k,如果有则res+=hashmap[pre_sum-k]

class Solution:def subarraySum(self, nums: List[int], k: int) -> int:hashmap = {0:1}tsum = 0 res = 0for i in range(len(nums)):tsum += nums[i]if tsum - k in hashmap:res += hashmap[tsum-k]if tsum in hashmap:hashmap[tsum] += 1else :hashmap[tsum] = 1return res