题目描述
思路解析
一句话答案：LeetCode 560 和为 K 的子数组的标准解是前缀和加哈希表一次遍历：子数组和等于两个前缀和之差，所以边扫边查 preSum - k 此前出现过几次、答案就加几，再把当前前缀和计入表中。数组含负数导致滑动窗口失效，这个方法不受影响，时间 O(n)、空间 O(n)。
这道题真正在问什么
题目给数组 nums 和整数 k，统计「连续子数组」——也就是一段下标相邻的元素——的和恰好等于 k 的个数。两个关键点：数组可能含负数，子数组之间可以重叠；要的只是个数，不需要返回具体位置。示例 nums = [1,2,3,-1,1,1,2,3]、k 取 3 时答案是 6，可见同一个位置可以同时属于多段答案。
为什么滑动窗口在这题会失效
很多人先想到滑动窗口：和小了扩右边、和大了缩左边。但窗口伸缩依赖一个前提——往里加数窗口和一定变大、往外扔数一定变小。数组一旦含负数，这个单调性就没了：扩窗可能让和变小，缩窗可能让和变大，指针不知道该往哪动。退回暴力做法「枚举每个起点、往后逐个累加」，时间是 O(n²)，数组一大就太慢。
子数组和为什么等于前缀和之差
关键观察：记前缀和 preSum 为从头累加到某个位置的总和，那么任意一段子数组的和，都等于「右端点处的前缀和」减「左端点前一位的前缀和」。于是「以当前位置结尾、和为 k 的子数组有几个」，等价于「更早的位置里，前缀和恰好等于 preSum - k 的有几个」。这一步把「枚举区间」翻译成「查一个确定的值出现过几次」，而后者正是哈希表 O(1) 能回答的——和两数之和里查 target - x 是同一招，只是把「值」换成了前缀和、把「下标」换成了出现次数。
解法随之成形：建一张表记录「前缀和的值 → 出现次数」，从左到右扫数组，每到一个数先累加出当前前缀和，查表里 preSum - k 出现过几次、答案就加几，然后把当前前缀和的计数加一，留给后面的位置查。
为什么要预置 0 出现 1 次、先查后存
表里一开始必须放一条「前缀和 0 出现 1 次」，它代表空前缀。少了它，「从下标 0 开始、整段恰好等于 k」的子数组会被漏数——这种情况下要查的 preSum - k 恰好等于 0，表里必须能查到。
循环体内先查 preSum - k、再把 preSum 存进表，顺序不能反。先存后查会把自己也当成候选：当 k 为 0 时 preSum - k 就等于 preSum 本身，先存就会查到自己、凭空多数一段长度为 0 的「子数组」。先查后存保证查到的永远是严格更早的前缀，对应的子数组长度至少为 1。
复杂度怎么算，还有哪些坑
时间 O(n)：每个数只做一次累加、一次查表、一次计数，均摊都是 O(1)。空间 O(n)：最坏时几乎所有不同的前缀和都要进表。另一个常见错误是往表里存前缀和出现的下标——本题只数个数，存「出现次数」就够了；存下标是「返回具体位置或最长长度」那类变体才需要的。如果题目改成「和能被 k 整除的子数组个数」，把哈希键换成前缀和对 k 取模的余数，同一套框架照用。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住「子数组和 = 两个前缀和之差」——下面每一帧都在套：查 preSum − k 出现过几次，就加几条。
关键的起手式：哈希表先放一条 {前缀和 0 → 出现 1 次}。它代表「空前缀」——这样「从下标 0 开始、整段正好等于 k」的子数组也能被数到。
当前前缀和 preSum = 1，need = 1 − 3 = -2。表里没有 -2(出现 0 次)，所以以下标 0 结尾、和为 3 的子数组这一步一条也没有。
处理完查找，把当前前缀和 1 记进表里(出现次数 +1)。注意是「先查后存」：先用旧表回答了当前位置，再把自己加进去，给后面的数当依据。
当前前缀和 preSum = 3，要找的另一头 need = 3 − 3 = 0。表里 0 出现过 1 次——说明有 1 个更早的位置，从那之后到这里这一段的和正好是 3。
绿色高亮的就是新数出来的 1 段：起点 0 到下标 1，每段加起来都正好 3。把这 1 条计入答案，cnt 从 0 变成 1。
处理完查找，把当前前缀和 3 记进表里(出现次数 +1)。注意是「先查后存」：先用旧表回答了当前位置，再把自己加进去，给后面的数当依据。
当前前缀和 preSum = 6，要找的另一头 need = 6 − 3 = 3。表里 3 出现过 1 次——说明有 1 个更早的位置，从那之后到这里这一段的和正好是 3。
绿色高亮的就是新数出来的 1 段：起点 2 到下标 2，每段加起来都正好 3。把这 1 条计入答案，cnt 从 1 变成 2。
处理完查找，把当前前缀和 6 记进表里(出现次数 +1)。注意是「先查后存」：先用旧表回答了当前位置，再把自己加进去，给后面的数当依据。
当前前缀和 preSum = 5，need = 5 − 3 = 2。表里没有 2(出现 0 次)，所以以下标 3 结尾、和为 3 的子数组这一步一条也没有。
处理完查找，把当前前缀和 5 记进表里(出现次数 +1)。注意是「先查后存」：先用旧表回答了当前位置，再把自己加进去，给后面的数当依据。
当前前缀和 preSum = 6，要找的另一头 need = 6 − 3 = 3。表里 3 出现过 1 次——说明有 1 个更早的位置，从那之后到这里这一段的和正好是 3。
绿色高亮的就是新数出来的 1 段：起点 2 到下标 4，每段加起来都正好 3。把这 1 条计入答案，cnt 从 2 变成 3。
处理完查找，把当前前缀和 6 记进表里(出现次数 +1)。注意是「先查后存」：先用旧表回答了当前位置，再把自己加进去，给后面的数当依据。
当前前缀和 preSum = 7，need = 7 − 3 = 4。表里没有 4(出现 0 次)，所以以下标 5 结尾、和为 3 的子数组这一步一条也没有。
处理完查找，把当前前缀和 7 记进表里(出现次数 +1)。注意是「先查后存」：先用旧表回答了当前位置，再把自己加进去，给后面的数当依据。
当前前缀和 preSum = 9，要找的另一头 need = 9 − 3 = 6。表里 6 出现过 2 次——说明有 2 个更早的位置，从那之后到这里这一段的和正好是 3。
绿色高亮的就是新数出来的 2 段：起点 3、5 到下标 6，每段加起来都正好 3。把这 2 条计入答案，cnt 从 3 变成 5。
处理完查找，把当前前缀和 9 记进表里(出现次数 +1)。注意是「先查后存」：先用旧表回答了当前位置，再把自己加进去，给后面的数当依据。
当前前缀和 preSum = 12，要找的另一头 need = 12 − 3 = 9。表里 9 出现过 1 次——说明有 1 个更早的位置，从那之后到这里这一段的和正好是 3。
绿色高亮的就是新数出来的 1 段：起点 7 到下标 7，每段加起来都正好 3。把这 1 条计入答案，cnt 从 5 变成 6。
处理完查找，把当前前缀和 12 记进表里(出现次数 +1)。注意是「先查后存」：先用旧表回答了当前位置，再把自己加进去，给后面的数当依据。
回看整条路径：指针只走一遍，每个位置查一次表、存一次前缀和。这就是 O(n)——比「枚举每个起点再往后逐个累加」的 O(n²) 快得多，且天然支持负数。
边界先想清：有负数/有 0 时暴力枚举容易错，前缀和+哈希照样正确，因为它只看「前缀和之差」。
三个高频追问：有负数为什么不能滑窗、如何推广到整除、以及和两数之和的同源关系。
参考代码
def subarraySum(nums, k): from collections import defaultdict cnt = defaultdict(int) cnt[0] = 1 # 空前缀: 前缀和0出现1次 preSum = ans = 0 for x in nums: preSum += x ans += cnt[preSum - k] # 查 need 出现几次 cnt[preSum] += 1 # 再把当前前缀和存进去 return ans复杂度
- 时间：O(n)，每个数只累加一次、查一次、存一次哈希，遍历一遍
- 空间：O(n)，最坏要把几乎所有不同的前缀和都存进哈希表
易错点
面试追问把动画讲成自己的话
追问为什么不用滑动窗口？
追问如果要求的是「和能被 k 整除」的子数组个数呢？
追问这题和两数之和的关系？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最短无序连续子数组
LeetCode 581 · 中等 · 沿着 数组 & 哈希 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题