知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 02 - 和为 K 的子数组 ## 题目(LeetCode 560) 给定数组 nums 和整数 k,统计和为 k 的连续子数组的个数。 ``` 输入:nums=[1,1,1], k=2 输出:2([1,1] 出现两次) 输入:nums=[1,2,3], k=3 输出:2([1,2] 和 [3]) ``` ## 大白话理解 暴力做法:枚举所有子数组算和,O(n²)。 前缀和 + HashMap:遍历一遍,边算前缀和边查 HashMap。 ``` 核心等式:prefix[j] - prefix[i] = k 即:prefix[i] = prefix[j] - k 遍历到 j 时,前缀和为 curSum 查 HashMap 中 curSum - k 出现了几次 → 就有几个子数组和为 k ``` ## 代码 ```java public int subarraySum(int[] nums, int k) { Map<Integer, Integer> prefixCount = new HashMap<>(); prefixCount.put(0, 1); // 前缀和为 0 出现 1 次 int curSum = 0, count = 0; for (int num : nums) { curSum += num; // 查找有多少个前缀和等于 curSum - k count += prefixCount.getOrDefault(curSum - k, 0); // 记录当前前缀和 prefixCount.put(curSum, prefixCount.getOrDefault(curSum, 0) + 1); } return count; } ``` > 💬 **Q:举例解释,还是有点抽象** > > 用 `nums = [1, 2, 3]`,`k = 3` 走一遍: > > ``` > 初始状态:prefixCount = {0: 1},curSum = 0,count = 0 > > 第 1 步:num = 1 > curSum = 0 + 1 = 1 > 查找 curSum - k = 1 - 3 = -2 → map 里没有 → count += 0 > 记录:prefixCount = {0:1, 1:1} > > 第 2 步:num = 2 > curSum = 1 + 2 = 3 > 查找 curSum - k = 3 - 3 = 0 → map 里有 {0:1} → count += 1 → count = 1 > ↑ 前缀和从 0 到 3,差值刚好是 k=3 → 子数组 [1,2] 的和为 3 > 记录:prefixCount = {0:1, 1:1, 3:1} > > 第 3 步:num = 3 > curSum = 3 + 3 = 6 > 查找 curSum - k = 6 - 3 = 3 → map 里有 {3:1} → count += 1 → count = 2 > ↑ 前缀和从 3 到 6,差值刚好是 k=3 → 子数组 [3] 的和为 3 > 记录:prefixCount = {0:1, 1:1, 3:1, 6:1} > > 结果:count = 2,对应子数组 [1,2] 和 [3] ✓ > ``` > > 本质就是 **Two Sum 的变体**:Two Sum 是在数组里找两个数之差等于 target,这里是找两个前缀和之差等于 k。`prefixCount` 就相当于 Two Sum 里的那个 HashMap,边遍历边查边存。 > > `put(0, 1)` 的作用:当 `curSum` 刚好等于 k 时,`curSum - k = 0` 需要在 map 里找到,表示"从数组开头到当前位置"这整段子数组的和就是 k。 ### 为什么初始化 `put(0, 1)`? 处理从数组开头开始的子数组。如果 curSum 本身就等于 k,那 curSum - k = 0,需要在 map 中找到 0。 ### 为什么不能用滑动窗口? 因为数组中可能有负数。滑动窗口要求窗口扩大时和增大、缩小时和减小,负数会破坏这个单调性。 ## 模拟 ``` nums=[1,2,3], k=3 num=1: curSum=1, 查 1-3=-2 → 0次, map={0:1, 1:1} num=2: curSum=3, 查 3-3=0 → 1次, map={0:1, 1:1, 3:1}, count=1 num=3: curSum=6, 查 6-3=3 → 1次, map={0:1, 1:1, 3:1, 6:1}, count=2 答案:2(子数组 [1,2] 和 [3])✓ ``` ## 复杂度 - 时间:O(n) - 空间:O(n) ## 一句话总结 边算前缀和边查 HashMap,`curSum - k` 在 map 中出现几次就有几个合法子数组。 --- 上一篇:[01 - 模板](./01-template.md) | 下一篇:[03 - 连续数组](./03-contiguous-array.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入