刷题记录## 2026-06-16 双指针128.最长连续序列二刷复盘这次踩坑点- SetInteger 一开始少写了 new说明集合初始化的基本写法还不够稳- res 一开始没初始化成 0导致答案变量的起点没立住- 我虽然记得“不是起点就跳过”但还是容易漏掉 continue- while 里一开始只写了 count没写 start这会让连续段没有真正往后推进甚至卡成死循环- 我一开始写了 res count这说明我又差点把“当前这段长度”和“历史最大值”混掉正确写法重点- 集合初始化SetInteger 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);- 构造分组 keyString key new String(chars);- 桶已存在时map.get(key).add(str);- 桶不存在时先 ListString 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-17283.移动零二刷复盘为什么 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-2249.字母异位词分组三刷复盘这次踩坑点- 我已经知道要用 str - chars - 排序 - key 这条链来构造分组特征但在新建桶时还是漏掉了“把当前字符串先放进桶里”这一步- 我一开始写成了只 map.put(key, list)结果第一次遇到某个 key 时桶是空的当前字符串直接丢了- 这说明我现在不是判型不会而是“新桶建立后要立刻装入当前元素”这个动作还不够自动化- list.add(str) 的返回值是 boolean正确写法重点- 生成 keychar[] chars str.toCharArray(); Arrays.sort(chars); String key new String(chars);- 桶已存在map.get(key).add(str);- 桶不存在ListString 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);- 遍历对象要用 setfor (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 0left- sum 0right--- sum 0收集答案然后 left、right--再分别跳过左右重复值今天最该记住的分界线- i 去重防止同一个开头值重复起手- left/right 去重防止同一组三元组重复加入结果- sum 0 移 leftsum 0 移 right因为排序后只有这样才有明确的“变大/变小”方向记住一句话- 先排序固定 i再用 left/right 夹出两数和找到答案后i 和左右两边都要去重## 2026-06-2315.三数之和二刷复盘这次踩坑点- 我一开始把 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] leftMaxres leftMax - height[left];- 否则更新leftMax height[left];- 然后 left- 否则处理右边- height[right] rightMaxres rightMax - height[right];- 否则更新rightMax height[right];- 然后 right--今天最该记住的分界线- leftMax rightMax左边当前格的水位已经由 leftMax 决定可以直接处理左边- 否则处理右边因为右边当前格的水位已经由 rightMax 决定- 如果代码是“先处理当前位置再移动指针”那这题要特别警惕left right 时那一格可能还没处理过记住一句话- 哪边最大值更小就先结算哪边这版写法要用 while(left right)别漏掉最后一格## 2026-06-243.无重复字符的最长子串第一次刷题题型信号- 题目给的是 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 语法基础点不够稳- HashMapchar, Integer 应该写成 HashMapCharacter, Integer- containskey 应该是 containsKey- toArrays / toCharArray 方法名容易写乱而且 toCharArray() 后面必须带 ()正确写法重点- 先准备哈希表HashMapCharacter, 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-2542.接雨水二刷复盘这次踩坑点- 我一开始又把 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右边看 right3.无重复字符的最长子串二刷复盘这次踩坑点- 我一开始又把 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-26438.找到字符串中所有字母异位词第一次刷题题型信号- 输入是两个字符串 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;- HashMapInteger, 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-k239.滑动窗口最大值第一次刷题题型信号- 输入是数组 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 里的双端队列写法- 这题常用写法是DequeInteger 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];- 双端队列DequeInteger 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 用单调递减队列维护窗口候选最大值窗口没形成时只维护形成后队头就是答案图解