和为 K 的子数组-python-前缀和&哈希表
·
题目：
思路：
前缀和的概念：
数组：nums[1,2,3]
前缀和：sum=[0,1,3,6].这里要注意len(sum)的长度比len(nums)大一，且第一位是0
这样做是为了num[0]也有之前的前缀和
- nums[i..j]=k可以变化成sum[j]-sum[i]=k,简单变化sum[j]=k-sum[i]
- 遍历到j的时候去之前的前缀和中找以target = k-sum[i]为key的value值（即target出现的次数）,答案加上这个值。
- 存入自身到哈希表{sum[j]:sum[j]这个前最缀和出现次数+1）}
代码：
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
ans = 0
mp = defaultdict(int) #哈希表，默认value都是0，表示出现次数为0
mp[0] =1
pre = 0 #初始化前缀和
for num in nums:
pre += num
target = pre - k
ans += mp.get(target,0)
mp[pre] += 1
return ans
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
4
0- 0
已为社区贡献30条内容
所有评论(0)