LeetCode 热题100：和为 K 的子数组（Java 实现详解）
本文将深入剖析 LeetCode 第560题《和为 K 的子数组》，从暴力枚举到前缀和 + 哈希表优化，全面讲解如何在 O(n) 时间内高效统计连续子数组和为 k 的个数。内容涵盖解题思路、代码实现、复杂度分析、面试高频问题及实际应用场景。
📌 原题回顾
题目描述：
给你一个整数数组nums和一个整数k，请你统计并返回该数组中和为k的子数组的个数。
子数组：数组中元素的连续非空序列。
示例
输入：nums = [1,1,1], k = 2 输出：2 解释：[1,1]（索引0~1）和 [1,1]（索引1~2） 输入：nums = [1,2,3], k = 3 输出：2 解释：[1,2] 和 [3]约束条件
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
🔍 原题分析
本题要求统计所有连续子数组中和等于 k 的数量。
关键点：
- 子数组必须连续；
- 元素可正可负，因此不能提前终止（负数可能使后续和再次等于 k）；
- 暴力法时间复杂度高，需寻找更优解。
常见误区：
- 误用滑动窗口（仅适用于全正数或单调性场景）；
- 忽略前缀和中“0”的初始状态。
💡 答案构思
方法一：暴力枚举（O(n²)）
对每个起始位置i，向左累加（或向右），检查是否存在子数组和为k。
虽然可行，但面对
n=2e4时，操作次数高达 2e8，可能超时。
方法二：前缀和 + 哈希表（O(n)）✅ 推荐
核心思想
- 定义前缀和
pre：pre[i] = nums[0] + nums[1] + ... + nums[i] - 若存在子数组
nums[j..i]满足sum = k，则：pre[i] - pre[j-1] = k ⇒ pre[j-1] = pre[i] - k - 因此，对于当前前缀和
pre，只需知道之前有多少个前缀和等于pre - k。
关键技巧
- 使用
HashMap记录每个前缀和出现的次数； - 初始化
map.put(0, 1)：表示前缀和为 0 出现 1 次（对应空子数组，用于处理从索引 0 开始的子数组）。
✅ 完整答案（Java）
方法一：暴力枚举（不推荐，仅作对比）
publicclassSolution{publicintsubarraySum(int[]nums,intk){intcount=0;for(intstart=0;start<nums.length;start++){intsum=0;for(intend=start;end>=0;end--){sum+=nums[end];if(sum==k){count++;}}}returncount;}}方法二：前缀和 + 哈希表（最优解）
importjava.util.HashMap;publicclassSolution{publicintsubarraySum(int[]nums,intk){intcount=0;intpre=0;// 当前前缀和HashMap<Integer,Integer>map=newHashMap<>();map.put(0,1);// 重要！前缀和为0出现1次（空子数组）for(intnum:nums){pre+=num;// 查找是否存在 pre - kif(map.containsKey(pre-k)){count+=map.get(pre-k);}// 更新当前前缀和的出现次数map.put(pre,map.getOrDefault(pre,0)+1);}returncount;}}🧠 代码分析
map.put(0, 1)：这是最容易忽略的点！
例如nums = [3], k = 3，当pre = 3时，需要pre - k = 0，若 map 中没有 0，则会漏掉这个解。- 累加顺序：先查
pre - k，再更新map，避免将当前前缀和自身计入（防止 j > i）。 - 负数支持：由于允许负数，前缀和可能重复、递减，哈希表能正确处理。
⏱️ 时间复杂度 & 空间复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(n²) | O(1) | 双重循环，内层累加 O(1) |
| 前缀和 + 哈希表 | O(n) | O(n) | 单次遍历，哈希表最坏存 n 个不同前缀和 |
在
n = 2e4时，O(n) 与 O(n²) 性能差距巨大，后者可能超时。
❓ 问题解答（FAQ）
Q1：为什么不能用滑动窗口？
A：滑动窗口要求“窗口扩大时和单调增加”，但本题含负数，窗口扩大后和可能变小，无法保证单调性。
Q2：如果 k 很大（如 1e9），会影响哈希表吗？
A：不会。哈希表 key 是前缀和（int 范围内），与 k 大小无关，只与pre - k是否存在于 map 中有关。
Q3：能否用数组代替 HashMap？
A：不行。前缀和范围可能很大（如[-2e7, 2e7]），无法用数组索引，且有负数。
🚀 优化思路
本题的 O(n) 解法已是最优，但可注意以下工程细节：
- 使用
getOrDefault避免 NPE； - 避免重复计算
pre - k，可缓存为变量； - 考虑溢出：虽然题目未要求，但若
nums[i]极大，可用long存pre。
// 防溢出版本（本题无需，但好习惯）longpre=0;Map<Long,Integer>map=newHashMap<>();📚 数据结构与算法基础知识点回顾
| 知识点 | 说明 |
|---|---|
| 前缀和（Prefix Sum） | 快速计算任意区间和：sum[i..j] = pre[j] - pre[i-1] |
| 哈希表（HashMap） | O(1) 插入/查询，用于记录历史状态频次 |
| 子数组 vs 子序列 | 子数组必须连续，子序列可不连续 |
| 初始化边界条件 | map.put(0, 1)是解决“从头开始”子数组的关键 |
💬 面试官提问环节（模拟）
Q：如果数组全是正数，能否用双指针？
A：可以！此时前缀和单调递增，可用滑动窗口：
- 若当前和 < k，右指针右移；
- 若当前和 > k，左指针右移；
- 若等于 k，计数并移动指针。
Q：如何修改代码以返回所有满足条件的子数组（而不仅是数量）？
A：需记录每个前缀和对应的索引列表，当pre - k存在时，遍历其索引列表生成子数组。但空间复杂度上升。
Q：如果要求子数组长度至少为 L，怎么改？
A：可在哈希表中存储<前缀和, Deque<索引>>，每次查询时只取索引 ≤ i - L 的项。
🛠️ 实际开发中的应用场景
- 金融交易系统：统计某段时间内累计收益等于目标值的交易区间；
- 日志分析：查找连续请求耗时总和等于阈值的时间窗口；
- 物联网数据流：检测传感器数据中是否存在累计偏差为 k 的时间段；
- 游戏开发：判断玩家连续得分是否达到某个奖励阈值。
🔗 相关题目推荐
| 题号 | 题目 | 关联点 |
|---|---|---|
| LeetCode 560 | 本题 | — |
| LeetCode 523 | 连续的子数组和 | 前缀和 + 同余定理 |
| LeetCode 525 | 连续数组 | 前缀和 + 0/1 平衡 |
| LeetCode 974 | 和可被 K 整除的子数组 | 前缀和 + 模运算 |
| LeetCode 724 | 寻找数组的中心下标 | 前缀和应用 |
📝 总结与延伸
本题是前缀和 + 哈希表的经典应用，展示了如何将 O(n²) 问题优化至 O(n)。
核心思想提炼：
- 将“区间和”问题转化为“前缀和差值”问题；
- 利用哈希表记录历史状态，实现 O(1) 查询；
- 正确处理边界条件（如前缀和为 0）。
延伸思考：
- 若数组动态更新（如支持单点修改），可使用树状数组（Fenwick Tree）或线段树维护前缀和；
- 若 k 为变量（多次查询），可预处理所有前缀和并排序，用二分查找（但本题 k 固定，哈希更优）。
掌握前缀和思想，你就拥有了处理“区间和”类问题的利器！
✅建议动手实现两种方法，对比性能差异，加深理解。
👉 如果你觉得本文对你有帮助，欢迎点赞、收藏、评论！也欢迎关注我的 CSDN 主页，获取更多高质量算法解析。
