考察点:把「子数组和等于 K」转化为「pre[j]-pre[i]=K 即 pre[i]=pre[j]-K」的计数问题;用哈希表在 O(n) 内统计前缀和频次。属场景题。
要点:
nums[i..j] 和为 K 等价于 pre[j+1] - pre[i] = K,即对每个右端点 j 需要找有多少个左端点 i 满足 pre[i] = pre[j+1] - K。cnt 记录「已出现的前缀和值 → 出现次数」。每到一个前缀和 cur,答案累加 cnt[cur - K](之前有多少个前缀和等于 cur-K),再把 cur 自身计数 +1。 def subarraySum(nums, k):
cnt = {0: 1}
cur = ans = 0
for x in nums:
cur += x
ans += cnt.get(cur - k, 0)
cnt[cur] = cnt.get(cur, 0) + 1
return ans
cnt={0:1}:处理「前缀和本身就等于 K」的情形(从下标 0 开始的子数组)。题目与答案就在本页;收藏、批注和错题重练在应用内