26.16-26
刷题记录
## 2026-06-16 双指针
128.最长连续序列（二刷复盘）
这次踩坑点：
- `Set<Integer>` 一开始少写了 `new`，说明集合初始化的基本写法还不够稳
- `res` 一开始没初始化成 `0`，导致答案变量的起点没立住
- 我虽然记得“不是起点就跳过”，但还是容易漏掉 `continue`
- `while` 里一开始只写了 `count++`，没写 `start++`，这会让连续段没有真正往后推进，甚至卡成死循环
- 我一开始写了 `res = count`，这说明我又差点把“当前这段长度”和“历史最大值”混掉
正确写法重点：
- 集合初始化：`Set<Integer> set = new HashSet<>();`
- 先把所有数字放进 `set`
- 遍历 `set` 时，若 `set.contains(num - 1)`，直接 `continue`
- 只有起点才继续：`int start = num; int count = 1;`
- 连续段扩展：`while (set.contains(start + 1)) { start++; count++; }`
- 维护历史最大值：`res = Math.max(res, count);`
记住一句话：
- `只从起点出发，边推进边计数，最后用 res 保留历史最大值`
49.字母异位词分组（二刷复盘）
这次踩坑点：
- 我一开始还是容易“先建空桶再判断是否存在”，结果会把同组里前面已经存进去的字符串覆盖掉
- 我虽然知道要按排序后的字符串分组，但还是容易把原字符串 `str` 和分组特征 `key` 混着用
- `List` 和 `ArrayList` 的关系还不够稳，写到“新建列表”时容易直接 `new List<>()`
- `String -> char[] -> 排序 -> String` 这条转换链还没完全熟
- 最后返回结果时，我知道答案在 `value` 里，但 Java 里是 `values()` 方法，不是 `value`
正确写法重点：
- 字符串转字符数组：`char[] chars = str.toCharArray();`
- 排序字符数组：`Arrays.sort(chars);`
- 构造分组 key：`String key = new String(chars);`
- 桶已存在时：`map.get(key).add(str);`
- 桶不存在时：先 `List<String> list = new ArrayList<>();`，再 `list.add(str);`，最后 `map.put(key, list);`
- 返回结果时：`return new ArrayList<>(map.values());`
记住一句话：
- `原字符串负责进桶，排序后的 key 负责找桶`
283.移动零
这次踩坑点：
- 我一开始容易把这题想成“找零再交换”的题，而不是“把非零元素稳定地收紧到前面”
- 我差点把 `slow` 理解成“找下一个零的位置”，但更准确地说，它表示“下一个非零元素应该放到哪里”
- 写交换时，我一开始想交换 `fast` 和 `slow` 这两个指针变量本身，而不是交换 `nums[fast]` 和 `nums[slow]`
- 我差点把 `if(fast != slow)` 放成外层判断，这会漏掉 `fast == slow` 但当前元素是非零时 `slow` 也应该前进的情况
- 这题不是每次遇到非零都必须真的交换，只有 `fast != slow` 时交换才有意义
正确写法重点：
- 初始化双指针：`int slow = 0;`
- 用 `fast` 扫描数组：`for (int fast = 0; fast < nums.length; fast++)`
- 只处理非零元素：`if (nums[fast] != 0)`
- 如果 `fast != slow`，交换 `nums[fast]` 和 `nums[slow]`
- 只要处理了一个非零元素，不管有没有交换，都要 `slow++`
## 2026-06-17
283.移动零（二刷复盘）
为什么 `slow++` 能指到下一个该放非零的位置：
- `slow` 维护的不是“下一个零的位置”，而是“下一个非零元素应该放的位置”
- 每当执行到 `slow++`，说明当前这一轮已经成功处理完了一个非零元素
- 这个非零元素要么本来就在 `slow` 位置上，要么刚刚被交换到了 `slow` 位置上
- 所以当前位置已经被一个合法的非零元素占好，下一次当然应该往后一个位置放新的非零元素
- 换句话说，`slow` 也可以理解成“前面已经整理好的非零区长度”
记住一句话：
- `fast 找非零，slow 指向下一个非零该放的位置`
11.盛最多水的容器
题型信号：
- 输入是数组 `height`，目标是从两端选两条线，让面积最大
- 面积由“较矮高度”和“两指针距离”共同决定：`area = min(height[left], height[right]) * (right - left)`
- 暴力枚举两条线是 `O(n^2)`，优化方向是相向双指针
这次理解重点：
- 面积的高度由较矮的那条线决定，不是由高的那条线决定
- 每次移动指针后，宽度一定变小，所以未来面积想变大，只能希望短板变高
- 因此应该移动较矮的一边，而不是移动较高的一边
正确写法重点：
- 初始化：`int left = 0; int right = height.length - 1; int res = 0;`
- 循环条件：`while (left < right)`，因为两条不同的线才能形成容器
- 当前面积：`int area = Math.min(height[left], height[right]) * (right - left);`
- 更新最大值：`res = Math.max(res, area);`
- 移动短板：如果 `height[left] < height[right]`，就 `left++`，否则 `right--`
易错点：
- `right` 初始化为 `height.length - 1`，不是 `height.length`
- 面积高度要用 `Math.min(...)`，不能用较高的那条线
- 移动指针时要移动较矮的一边，因为短板才是当前面积瓶颈
记住一句话：
- `宽度一定变小，所以移动短板，赌下一个短板更高`
## 端午休息
## 2026-06-22
49.字母异位词分组（三刷复盘）
这次踩坑点：
- 我已经知道要用 `str -> chars -> 排序 -> key` 这条链来构造分组特征，但在新建桶时还是漏掉了“把当前字符串先放进桶里”这一步
- 我一开始写成了只 `map.put(key, list)`，结果第一次遇到某个 `key` 时，桶是空的，当前字符串直接丢了
- 这说明我现在不是判型不会，而是“新桶建立后要立刻装入当前元素”这个动作还不够自动化
- `list.add(str)` 的返回值是 `boolean`
正确写法重点：
- 生成 key：`char[] chars = str.toCharArray(); Arrays.sort(chars); String key = new String(chars);`
- 桶已存在：`map.get(key).add(str);`
- 桶不存在：`List<String> list = new ArrayList(); list.add(str); map.put(key, list);`
- 返回结果：`return new ArrayList<>(map.values());`
记住一句话：
- `先把当前字符串装进新桶，再把桶挂到 key 上`
128.最长连续序列（三刷复盘）
这次踩坑点：
- 我这次主逻辑已经写对了，但提交时超时，暴露出我还没有把“遍历 `set` 而不是遍历 `nums`”这件事彻底自动化
- 如果遍历 `nums`，重复元素会让同样的数字被反复拿出来判断起点，虽然思路接近对，但效率会变差
- 这题真正稳定的写法是：先用 `set` 去重，再围绕 `set` 判断起点和扩展连续段
正确写法重点：
- 先去重：`for (int num : nums) set.add(num);`
- 遍历对象要用 `set`：`for (int num : set)`
- 起点判断：`if (set.contains(num - 1)) continue;`
- 从起点扩展：`while (set.contains(start + 1)) { start++; length++; }`
- 维护最长值：`res = Math.max(res, length);`
记住一句话：
- `先去重，再只从起点出发`
15.三数之和
题型信号：
- 题目要找的是“所有和为 `0` 的三元组”，而且结果不能重复
- 一边固定一个数，一边在剩余区间里继续找两数配合，更适合“排序 + 双指针”
- 这题不是随便设三个指针乱试，而是先排序，把“变大/变小”的方向交给有序数组
这次踩坑点：
- 我一开始还是按“直接凑三个下标”的方向写，`j++`、`k++` 这种写法没有真正利用有序性
- 我差点写成“两数之和找目标值”的变形，算 `0 - nums[i]`，但双指针这里更应该直接算三个数的和`int sum = nums[i]+nums[left]+nums[right]`
- 我一开始把 `i` 去重写成和后一个比较，实际上应该和前一个比，跳过的是“重复开头的第二个、第三个”
- 我写到 `sum == 0` 时，只做了 `left++`、`right--`，但还没立刻意识到后面要继续跳过重复值
- 我还一度把 `nums[left] != nums[right]` 当成是否加入答案的条件，但像 `[-2,1,1]` 这种合法答案会被误杀
正确写法重点：
- 先排序：`Arrays.sort(nums);`
- 固定开头：`for (int i = 0; i < nums.length; i++)`
- `i` 去重：`if (i > 0 && nums[i] == nums[i - 1]) continue;`
- 初始化双指针：`int left = i + 1; int right = nums.length - 1;`
- 在 `while (left < right)` 里直接算：`int sum = nums[i] + nums[left] + nums[right];`
- `sum < 0`：`left++`
- `sum > 0`：`right--`
- `sum == 0`：收集答案，然后 `left++`、`right--`，再分别跳过左右重复值
今天最该记住的分界线：
- `i` 去重：防止同一个开头值重复起手
- `left/right` 去重：防止同一组三元组重复加入结果
- `sum < 0` 移 `left`，`sum > 0` 移 `right`：因为排序后只有这样才有明确的“变大/变小”方向
记住一句话：
- `先排序，固定 i，再用 left/right 夹出两数和；找到答案后，i 和左右两边都要去重`
## 2026-06-23
15.三数之和（二刷复盘）
这次踩坑点：
- 我一开始把 `sum` 放在 `while` 外面，只算了一次，但 `left/right` 在循环里会变，`sum` 也必须每轮重新算
- 我把 `i` 去重写成了和后一个比较，甚至直接 `i++`，这会打乱 `for` 循环自己的节奏；正确思路是和前一个比，重复就 `continue`
- 我在 `sum == 0` 时一开始没有移动 `left/right`，这样会一直卡在同一组数上死循环
- 后来虽然知道要移动指针了，但又写成了“先移动、再记录答案”，结果加进去的不是刚刚命中的那组三元组
- 我还把 `list` 放错了位置，一度想让一个 `list` 承担一个 `i` 的所有结果，但其实每命中一次，都要新建一个三元组列表并立刻加入 `resList`
- 左右去重时，我又混淆了比较方向：`left` 已经右移后，要和 `left - 1` 比；`right` 已经左移后，要和 `right + 1` 比
正确写法重点：
- `sum` 要放在 `while (left < right)` 里每轮重算：`int sum = nums[i] + nums[left] + nums[right];`
- `i` 去重：`if (i > 0 && nums[i] == nums[i - 1]) continue;`
- `sum < 0`：只做 `left++`
- `sum > 0`：只做 `right--`
- `sum == 0`：先新建 `list` 收集 `nums[i]`、`nums[left]`、`nums[right]`，立刻 `resList.add(list)`，再 `left++`、`right--`
- `sum == 0` 后继续去重：
`while (left < right && nums[left] == nums[left - 1]) left++;`
`while (left < right && nums[right] == nums[right + 1]) right--;`
今天最该记住的分界线：
- `sum < 0 / > 0` 时只是移动一边，不急着去重
- 真正要做左右去重的时机，是 `sum == 0` 找到答案之后
- 记录答案的顺序是：`先记录，再移动，再去重`
记住一句话：
- `15 题最怕顺序乱：先算 sum，命中后先收集答案，再移动左右，再跳过重复`
42.接雨水
题型信号：
- 输入是柱状图高度数组，目标不是找区间和，而是算“每个位置上方最多能存多少水”
- 某个位置能接多少水，不取决于自己多高，而取决于它左右两侧的最高挡板里较矮的那个
- 这题可以先想到“预处理 `leftMax/rightMax`”，再进一步优化成“双指针 + 边走边维护最大值”
这次踩坑点：
- 我一开始差点把接水公式写反，正确的是 `min(leftMax, rightMax) - height[i]`
- 在预处理思路里，我一开始把 `leftMax[i]` 跟自己比了，但真正该比的是“前一个最大值”和“当前柱子高度”
- 切到双指针后，我已经知道 `leftMax < rightMax` 处理左边，否则处理右边，但右边分支一开始漏写了 `right--`
- 我最后真正提交出错的关键坑，是把循环条件写成了 `while(left < right)`，结果漏算了 `left == right` 时最后那个还没处理的位置，样例少算了 `1`
正确写法重点：
- 先判空：`if (height == null || height.length == 0) return 0;`
- 初始化：`int left = 0; int right = height.length - 1;`
- 维护两侧最高值：`int leftMax = height[left]; int rightMax = height[right];`
- 循环条件：`while (left <= right)`
- 如果 `leftMax < rightMax`，先处理左边：
- `height[left] < leftMax`：`res += leftMax - height[left];`
- 否则更新：`leftMax = height[left];`
- 然后 `left++`
- 否则处理右边：
- `height[right] < rightMax`：`res += rightMax - height[right];`
- 否则更新：`rightMax = height[right];`
- 然后 `right--`
今天最该记住的分界线：
- `leftMax < rightMax`：左边当前格的水位已经由 `leftMax` 决定，可以直接处理左边
- 否则处理右边，因为右边当前格的水位已经由 `rightMax` 决定
- 如果代码是“先处理当前位置，再移动指针”，那这题要特别警惕：`left == right` 时那一格可能还没处理过
记住一句话：
- `哪边最大值更小，就先结算哪边；这版写法要用 while(left <= right)，别漏掉最后一格`
## 2026-06-24
3.无重复字符的最长子串（第一次刷题）
题型信号：
- 题目给的是 `String`，目标是求“最长子串”的长度
- 这里的“子串”说明答案必须是连续区间，不是随便挑字符
- 题目还要求“无重复字符”，说明我们在维护一个合法窗口：窗口内不能出现重复
- 所以这题最典型的判型是：`滑动窗口 + 哈希表`
我这次是怎么一步步判出来的：
- 一开始先抓住了最关键的词：`子串`
- 因为是子串，所以我意识到它本质上是在字符串上维护一段连续区间
- 再加上“无重复”，就说明这个区间会随着新字符加入而变得不合法，需要动态收缩
- 所以这题不像普通哈希统计那样一次把全串数完，而是要一边扩张右边界，一边在必要时移动左边界
窗口里每个变量的角色：
- `left`：当前窗口左边界
- `right`：当前窗口右边界，负责一格一格向右扫描
- `map`：记录 `字符 -> 最近一次出现的位置`
- `res`：到目前为止的最长合法窗口长度
为什么 `map` 里要存“最近一次出现的位置”：
- 因为当 `right` 扫到一个重复字符时，我们关心的不是“它出现过没”，而是“它上次出现在当前窗口里的什么位置”
- 只有拿到这个位置，`left` 才知道要跳到哪里
- 这就是这题和单纯 `HashSet` 判重的区别：这里不仅要知道“重复了”，还要知道“重复点在哪”
这题最核心的更新句：
- 当当前字符 `c` 已经出现过时：
`left = Math.max(left, map.get(c) + 1);`
为什么一定要 `Math.max(...)`：
- 因为 `left` 只能往右走，不能往左退
- 我这次专门用 `abba` 这个例子想明白了：
- 当扫到最后一个 `a` 时，`a` 以前确实出现过
- 但它上一次出现的位置已经在当前窗口左边界外面了
- 如果我直接写 `left = map.get(c) + 1`，就会把 `left` 往回拉，窗口逻辑会乱
- 所以这里不是简单赋值，而是：
`left = Math.max(left, map.get(c) + 1)`
我这次写代码时暴露出来的坑：
- 一开始把 `right` 和 `i` 两套角色混用了，说明滑动窗口里“谁负责扫描”这个角色还不够稳
- 我一开始写了固定的 `right = 1`，但又想用 `for` 去遍历，这会让右边界角色混乱
- 我一开始差点每轮都 `left++`，但这题里 `left` 不是自动前进，而是“只有重复时才跳”
- 我一开始把 `map.put(...)` 和 `res = Math.max(...)` 都放进了 `if` 里，这会导致只有遇到重复时才更新，非重复字符反而没被正常纳入窗口
- 我还暴露出一些 Java 语法基础点不够稳：
- `HashMap<char, Integer>` 应该写成 `HashMap<Character, Integer>`
- `containskey` 应该是 `containsKey`
- `toArrays` / `toCharArray` 方法名容易写乱，而且 `toCharArray()` 后面必须带 `()`
正确写法重点：
- 先准备哈希表：`HashMap<Character, Integer> map = new HashMap<>();`
- 初始化：`int left = 0; int res = 0;`
- 把字符串转成字符数组：`char[] chars = s.toCharArray();`
- 用 `right` 扫描整个字符串：
`for (int right = 0; right < s.length(); right++)`
- 当前字符：`char c = chars[right];`
- 如果 `map` 里已经有这个字符：
`left = Math.max(left, map.get(c) + 1);`
- 不管重不重复，都要更新当前位置：
`map.put(c, right);`
- 再更新当前窗口长度：
`res = Math.max(res, right - left + 1);`
今天最该记住的分界线：
- `子串` -> 优先想到连续区间 -> 滑动窗口
- `无重复` -> 不是固定窗口，而是遇到重复时要动态收缩
- `HashSet` 只能判断“有没有”，`HashMap` 才能告诉我“重复点在哪”
- 这题里 `left` 不是每轮都加 1，而是只在重复时跳
- 跳的时候不能后退，所以一定要：
`left = Math.max(left, map.get(c) + 1)`
记住一句话：
- `right 负责扩张窗口，left 只在重复时跳；map 存最近位置，left 只能右移不能后退`
## 2026-06-25
42.接雨水（二刷复盘）
这次踩坑点：
- 我一开始又把 `leftMax` 和 `rightMax` 放回了 `while` 里面，每轮都重新等于当前位置高度，这样它们就不再是“历史最大值”，而只是“当前这一格”
- 我一开始把左右分支拆成了两套独立判断，导致一轮里可能连续处理两边，指针也会在同一轮里被多次移动
- 我还一度在每个分支里同时写了 `left++` 和 `right--`，但这题每一轮只能结算一边，所以一轮只能移动一个指针
- 右边分支我又把参与计算的柱子写错了，处理右边时应该看 `height[right]`，不是 `height[left]`
- 我还把右边分支的大小判断写反了：应该是“当前柱子更低才加水”，不是“当前柱子更高才加水”
- 这次重新暴露出一个核心问题：我知道了“比较 `leftMax` 和 `rightMax`”，但对“哪边分支该更新最大值、哪边分支该加水”还没有完全自动化
正确写法重点：
- `leftMax` 和 `rightMax` 在循环外初始化一次，进入循环后只按情况更新，不要每轮重置
- 主结构只有一层：
`if (leftMax < rightMax) { 处理 left } else { 处理 right }`
- 左边分支：
- 如果 `height[left] < leftMax`，就 `res += leftMax - height[left]`
- 否则更新 `leftMax = height[left]`
- 最后只做 `left++`
- 右边分支：
- 如果 `height[right] < rightMax`，就 `res += rightMax - height[right]`
- 否则更新 `rightMax = height[right]`
- 最后只做 `right--`
今天最该记住的分界线：
- `leftMax/rightMax` 是“历史最大值”，不是“当前高度”
- 一轮只能处理一边，所以一轮也只能移动一个指针
- 左右两边的逻辑是完全对称的：左边看 `height[left]`，右边看 `height[right]`
记住一句话：
- `42 二刷最容易乱的是角色：最大值别重置，一轮只处理一边，左边看 left，右边看 right`
3.无重复字符的最长子串（二刷复盘）
这次踩坑点：
- 我一开始又把 `left` 和 `right` 的角色写反了：把 `left` 写成了主动遍历的指针，但这题真正负责一格一格向右扫描的是 `right`
- 我一开始在 `for` 里面又手动写了 `right++`，这会让 `right` 每轮跳两格，窗口直接漏扫字符
- 我一开始把重复字符时的更新写成了 `left = right + 1`，这说明我还在用“跳过当前字符”的直觉，而不是“跳过旧重复字符”的位置
- 后来改成了 `left = map.get(c) + 1`，但这还不够稳，因为 `left` 可能会后退，`abba` 这种例子就会出错
- 这次再次说明：我已经知道这题是滑动窗口了，但一写代码还是容易把“谁负责扫描、谁只在必要时跳”这两个角色混掉
正确写法重点：
- `right` 负责遍历整个字符串：
`for (int right = 0; right < s.length(); right++)`
- `left` 不是每轮自动加 1，而是只在遇到重复字符时更新
- 遇到重复字符时，不能写成 `left = right + 1`
- 也不能简单写成 `left = map.get(c) + 1`
- 真正稳定的写法是：
`left = Math.max(left, map.get(c) + 1);`
- 然后正常更新：
`map.put(c, right);`
`res = Math.max(res, right - left + 1);`
今天最该记住的分界线：
- `right`：负责扩张窗口，正常往右扫
- `left`：只在重复时跳，平时不乱动
- `map.get(c) + 1` 给的是“理论上该跳到哪”，`Math.max(...)` 才能保证 `left` 不后退
记住一句话：
- `3 二刷最容易乱的是左右角色：right 负责扫，left 只在重复时跳，而且只能右移不能后退`
## 2026-06-26
438.找到字符串中所有字母异位词（第一次刷题）
题型信号：
- 输入是两个字符串 `s` 和 `p`
- 目标不是只判断一次 `true/false`，而是找出 `s` 中所有满足条件的子串起点
- 条件是：该子串和 `p` 互为字母异位词
- “异位词”本质上还是字符频次比较，所以这一层很像 `242`
- 但这里又多了“子串”，说明比较对象不是任意字符集合，而是 `s` 上一段连续区间
- 并且因为异位词长度必须和 `p` 一样，所以窗口长度是固定的
- 所以这题的第一次判型应该是：`固定长度滑动窗口 + 频次比较`
第一次刷题时我先建立的模型：
- 先统计 `p` 的频次表
- 再在 `s` 上拿一个长度为 `p.length()` 的窗口
- 判断当前窗口频次是否和 `p` 完全一致
- 如果一致，就把当前窗口左端点加入结果
- 这本质上就是：`438 = 242 的频次比较 + 固定窗口`
我一开始为什么会想到朴素写法：
- 因为第一次刷题时，最重要的是先把“窗口长度固定”和“比较频次”这两个核心模型搭起来
- 所以我一开始的自然思路是：
- 每个窗口都单独统计一份 `windowMap`
- 再用 `map.equals(windowMap)` 比较
- 这个思路虽然不够快，但它能帮我先确认题型和逻辑没有跑偏
第一次写代码时暴露出来的坑：
- 我一开始在统计 `p` 的频次时，写了一个局部 `count`，但每轮都会重新归零，说明我还没有完全把“频次累计”模板自动化
- 后来我意识到，这里应该直接用：
`map.put(c, map.getOrDefault(c, 0) + 1);`
- 我一开始拿到固定窗口时，`right` 的表达式写反了，没有真正体现“`right` 随着 `left` 一起往右滑”
- 我一开始最内层统计窗口频次时，一直重复统计 `charStrS[left]`，说明我虽然知道要遍历窗口，但还没真正把“窗口里的每一格都要扫到”落实到代码里
- 我一开始用 `map == windowMap` 比较两张表，这比较的是是不是同一个对象，不是内容是否相等；后来才改成了 `map.equals(windowMap)`
- 我一开始忘了比较初始窗口，结果会漏掉起点 `0`
- 我还暴露出一个边界问题：如果 `s.length() < p.length()`，应该直接返回空列表，而不是继续统计窗口
第一次刷题写通后的朴素解法思路：
- 一张 `map`：统计 `p` 的频次
- 每个窗口都临时建一张 `windowMap`
- 窗口范围是：
`left ... left + p.length() - 1`
- 每个窗口统计完后，用：
`map.equals(windowMap)`
判断是否为异位词
- 这版思路是对的，但复杂度偏高
为什么这版会超出时间限制：
- 因为我后来意识到：我虽然用了“滑动窗口”的窗口边界，但还没有真正利用“滑动”本身
- 我当时做的是：
- 每来到一个新窗口
- 就重新创建一张 `windowMap`
- 再把整个窗口从头到尾数一遍
- 这等于窗口虽然在滑，但频次表每次都重建
- 所以时间复杂度就变成了：
- 窗口个数很多
- 每个窗口又都重新统计整段
- 整体就会慢
优化复杂度时，我重新建立的正确滑窗模型：
- 既然窗口长度固定，窗口每次只向右滑 1 格
- 那么新窗口和旧窗口相比，只会发生两个变化：
- 旧的左端字符滑出窗口
- 新的右端字符滑入窗口
- 所以根本不需要重建整张 `windowMap`
- 只需要在已有频次表上做两次更新：
- `out`：频次 `-1`
- `in`：频次 `+1`
优化版里最关键的两个字符：
- 当新窗口左端点是 `left` 时：
- 滑出窗口的字符是：
`char out = charStrS[left - 1];`
- 滑入窗口的字符是：
`char in = charStrS[right];`
- 其中：
`right = left + p.length() - 1;`
为什么 `out` 要先减 1，再考虑删除：
- 因为一个字符滑出窗口时，不一定就完全消失了
- 它在窗口里可能还有别的副本，所以第一步应该是：
`windowMap.put(out, windowMap.get(out) - 1);`
- 只有当减完次数变成 `0` 时，才执行：
`windowMap.remove(out);`
- 不删掉次数为 `0` 的键，会影响后面 `map.equals(windowMap)` 的比较结果
优化版完整思路骨架：
- 先统计 `p` 的频次表 `map`
- 再统计 `s[0 ... p.length() - 1]` 的初始窗口频次 `windowMap`
- 先比较一次初始窗口，若相等就加入 `0`
- 然后让 `left` 从 `1` 开始滑动到最后一个合法起点
- 每轮：
- 算当前窗口右端点 `right`
- `out` 减 1，必要时删除
- `in` 加 1
- 再比较 `map.equals(windowMap)`
- 若相等，就把当前 `left` 加入结果
这题和之前题目的分界线：
- 和 `242` 的关系：
- `242` 只比较一次两个字符串频次
- `438` 是在 `s` 上不断取定长窗口，反复做 `242`
- 和 `3` 的关系：
- `3` 是可变窗口，窗口长度由“是否重复”动态收缩
- `438` 是固定窗口，窗口长度始终等于 `p.length()`
- 所以 `438` 不能按 `3` 那种“窗口不合法就一直缩”的思路写，而是要固定长度地往右平移
今天最该记住的分界线：
- `异位词` -> 看频次
- `子串` -> 看连续区间
- `和 p 同长度` -> 固定窗口
- `第一次刷题` 可以先每个窗口重建频次表，把题做对
- `超时后优化` 的关键不是换题型，而是让频次表随着窗口滑动做增量更新
记住一句话：
- `438 = 固定窗口版的 242；先把题做对，再把“每个窗口重建整张表”优化成“out--、in++”`
560.和为 K 的子数组（第一次刷题）
题型信号：
- 输入是 `int[] nums`，而且可能有 `负数`
- 目标是找 `连续子数组`
- 要求返回的是 `个数`，不是长度，也不是是否存在
- 只要出现 `连续子数组 + 求个数 + 可能有负数`，就要优先警觉：这题通常不是普通滑动窗口，而是 `前缀和 + HashMap`
我这次是怎么一步步判出来的：
- 我先抓到的是“子数组”，说明答案一定对应数组里的某一段连续区间
- 然后继续看，题目求的是“和等于 `k` 的子数组个数”
- 这时如果去枚举每个区间，复杂度会很高，所以就要想：能不能把“某段区间的和”转成“之前信息 + 当前信息”
- 这一步就会落到前缀和上：如果当前前缀和是 `pre`，想要某段区间和为 `k`，本质上就是找之前有没有前缀和等于 `pre - k`
- 因为题目求的是“个数”，所以 `HashMap` 里不能只存“有没有出现过”，而要存“某个前缀和出现过多少次”
这题最核心的数学关系：
- 设当前前缀和为 `pre`
- 如果某段子数组和为 `k`
- 那就说明：`当前前缀和 - 之前某个前缀和 = k`
- 也就是：`之前某个前缀和 = pre - k`
- 所以当我扫到当前位置时，只要知道 `pre - k` 之前出现过多少次，就知道“以当前位置结尾、和为 `k` 的子数组”有多少个
HashMap 在这题里到底存什么：
- `key`：某个前缀和
- `value`：这个前缀和出现的次数
- 也就是：`map.get(x)` 表示“前面前缀和等于 `x` 的情况出现过几次”
为什么一开始就要写 `map.put(0, 1)`：
- 它表示：在还没遍历任何元素之前，前缀和 `0` 已经出现过 `1` 次
- 这是为了处理“从下标 `0` 开始的那段子数组刚好和为 `k`”的情况
- 如果当前 `pre == k`，那我们就需要去找 `pre - k = 0`
- 这时候如果没有预先放入 `0 -> 1`，这类答案就会被漏掉
正确模板：
- 初始化：
- `int pre = 0;`
- `int res = 0;`
- `HashMap<Integer, Integer> map = new HashMap<>();`
- `map.put(0, 1);`
- 遍历数组中每个 `num`
- 先更新当前前缀和：`pre += num`
- 再查之前有多少个前缀和等于 `pre - k`：
- `res += map.getOrDefault(pre - k, 0);`
- 最后把当前前缀和记进表里：
- `map.put(pre, map.getOrDefault(pre, 0) + 1);`
这次我写代码时暴露出来的坑：
- 我一开始把
- `res += map.getOrDefault(pre - k, 0);`
写成了
- `res = map.getOrDefault(pre - k, 0);`
- 这说明我当时还没完全分清：
- `map.getOrDefault(pre - k, 0)` 表示“当前这一轮新找到几个”
- `res` 表示“到目前为止总共找到几个”
- 所以这里必须是“累加答案”，不能是“覆盖答案”
第二个坑：
- 我一开始把
- `map.put(pre, map.getOrDefault(pre, 0) + 1);`
少写了 `+1`
- 这会导致前缀和次数根本没有增长，相当于 `map` 没有正确记录历史出现次数
- 这题不是只看“这个前缀和存不存在”，而是严格依赖“它之前出现过几次”
第三个坑：
- 我一开始差点把 `pre` 和 `res` 写进循环里重新声明
- 但这两个变量都不是每轮临时值
- `pre` 是一路累计的前缀和
- `res` 是一路累计的总答案
- 所以它们必须在循环外初始化，在循环里只更新
第四个坑：
- 这题的顺序必须是：
- 先 `pre += num`
- 再查 `pre - k`
- 最后更新 `map` 里的 `pre`
- 不能先把当前 `pre` 放进 `map`
- 因为 `map` 里存的应该是“当前位置之前的前缀和统计”
- 先放再查，会把“当前这一位自己”提前算进历史里，语义就乱了
为什么这题不是普通滑动窗口：
- 因为数组里可能有 `负数`
- 一旦有负数，窗口和就不再具有“左缩小一定变小、右扩张一定变大”的单调性
- 所以不能靠滑动窗口那种“和大了就缩、和小了就扩”的方式稳定求解
- 这题真正稳定的思路是：不直接维护窗口和，而是维护“前缀和之间的差”
今天最该记住的分界线：
- `连续子数组 + 求个数 + 可能有负数`
-> 优先想 `前缀和 + HashMap`
- `HashMap` 里不是存下标，也不是存布尔值
-> 存的是 `前缀和 -> 出现次数`
- 这题的答案不是看“当前有没有”
-> 而是看“之前有多少个 `pre - k`”
记住一句话：
- `560 不是滑动窗口题，而是前缀和找差值：当前 pre 想凑出 k，就去 HashMap 里找之前出现过多少次 pre-k`
239.滑动窗口最大值（第一次刷题）
题型信号：
- 输入是数组 `nums`，再给一个固定窗口大小 `k`
- 窗口会从左往右滑动
- 每滑一次，都要立刻知道“当前窗口里的最大值”
- 这题不是普通双指针，也不是固定窗口里暴力找最大值，而是要维护一个“窗口滑动过程中还能竞争最大值的结构”
我这次是怎么判型的：
- 我先抓到的是“滑动窗口”这四个字，所以第一反应是窗口会不断有元素滑出、也不断有元素滑入
- 但这题和 `3`、`438` 不一样，不是维护一个合法性条件，也不是维护频次
- 它要维护的是“最大值”
- 如果每次窗口形成后都重新扫一遍找最大值，虽然思路直接，但复杂度会太高
- 所以这题真正的关键不是“窗口怎么动”，而是“窗口动的时候，怎么让最大值也能被快速维护”
为什么最后会落到单调队列：
- 如果一个新进来的数更大，而且它在更右边
- 那么它左边那些比它小的数，只要它们还和它同时待在窗口里，就永远不可能成为最大值
- 例如队尾是 `3`，新进来的是 `5`
- 只要 `5` 还在窗口中，`3` 就没有任何机会再当最大值
- 所以这些较小元素没有必要继续留在队列里
- 这就说明我们要维护一个“从大到小”的队列，也就是 `单调递减队列`
为什么队列里存的是下标，不是值：
- 因为窗口左边会不断滑出元素
- 我们必须知道队头这个元素“是不是已经不在当前窗口里了”
- 只有存下标，才能判断它是否已经过期
- 所以队列里存的是 `index`
- 但比较大小时，看的是 `nums[index]`
单调队列在这题里的角色：
- 队头：当前窗口最大值的下标
- 队列中下标对应的值：从队头到队尾单调递减
- 这样一来，当前窗口最大值就可以直接用：
`nums[deque.peekFirst()]`
每一轮固定做的 4 件事：
- 1. 先删掉已经滑出窗口左边界的下标
- 条件是：
`deque.peekFirst() < i - k + 1`
- 2. 再删掉队尾那些比当前值小的下标
- 条件是：
`nums[deque.peekLast()] < nums[i]`
- 3. 把当前下标 `i` 放到队尾
- 4. 只有当窗口真正形成后，才开始收集答案
这题最容易错的分界线：窗口“形成之前”和“形成之后”
- 当 `i < k - 1` 时，窗口还没凑够 `k` 个元素
- 这时候队列虽然已经在维护了，但还不能往结果数组里写答案
- 只有当：
`i >= k - 1`
时，当前窗口才第一次完整形成
- 也就是说：
- `i = 0, 1, ... , k-2`：只维护队列，不产出答案
- `i = k-1`：第一个完整窗口出现，开始产出第 1 个答案
为什么答案写在 `res[i - k + 1]`：
- 当遍历到 `i` 时，当前窗口右边界就是 `i`
- 固定长度是 `k`
- 所以当前窗口左边界就是：
`i - k + 1`
- 结果数组里，每个窗口对应一个答案
- 因此当前窗口最大值应该写到：
`res[i - k + 1]`
这次我写代码时暴露出来的坑：
- 我一开始把结果数组写成了：
`new int[k]`
- 但这题窗口一共会产生：
`nums.length - k + 1`
个答案
- 所以结果数组长度必须跟“窗口个数”一致，而不是跟 `k` 一样
第二个坑：
- 我一开始虽然已经知道要用队列，但还不会 Java 里的双端队列写法
- 这题常用写法是：
`Deque<Integer> deque = new LinkedList<>();`
- 重点不是死记 API，而是记住：
- `peekFirst / pollFirst`：看/删队头
- `peekLast / pollLast`：看/删队尾
- `offerLast`：从队尾加入
第三个坑：
- 我一开始把“收集答案”的时机放错了
- 我先写了：
`res[i - k + 1] = nums[deque.peekFirst()]`
- 然后才去删过期元素、删较小队尾、再把当前 `i` 入队
- 这样其实是在“窗口还没更新完”的时候，先拿旧答案
- 正确顺序必须是：
- 先删过期队头
- 再删较小队尾
- 再让当前下标入队
- 最后如果窗口形成了，再取队头作为答案
正确模板骨架：
- 结果数组：
`int[] res = new int[nums.length - k + 1];`
- 双端队列：
`Deque<Integer> deque = new LinkedList<>();`
- 遍历每个下标 `i`
- 先删过期下标：
`if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) deque.pollFirst();`
- 再删掉所有比当前值小的队尾：
`while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();`
- 当前下标入队：
`deque.offerLast(i);`
- 如果窗口已经形成：
`if (i >= k - 1) res[i - k + 1] = nums[deque.peekFirst()];`
今天最该记住的分界线：
- `3` 和 `438`：核心是“窗口是否合法”
- `239`：核心不是合法性，而是“窗口里谁还配竞争最大值”
- `239` 里队列不是按进入顺序单纯存元素
- 而是按“未来是否还有资格当最大值”来筛选保留
记住一句话：
- `239 = 用单调递减队列维护窗口候选最大值；窗口没形成时只维护，形成后队头就是答案`