标题里的“吃饭香”不是夸张是我这段时间重刷算法题的真实状态。第一次过 704、27、977 这三道题的时候我基本处于“抄一遍代码第二天就忘”的阶段边界条件稍微一改就全乱。到了二周目重新打开它们才意识到这套训练营把这三道题放在第一天根本不是随便凑数的704二分查找逼你把区间定义想清楚27移除元素带出快慢双指针这个基础范式977有序数组的平方又把双指针扩展成两端夹逼。三道题单独看都简单合在一起却覆盖了后面大部分题目的底层动作。这篇文章就是我在二周目第一天的完整记录包含每道题的思路拆解、可复制的代码模板、常见 bug 清单以及我在实际刷题过程中踩过的坑。适合刚入门算法、准备系统刷题或者正在二刷三刷的朋友参考。1. 第一天三道题的设计逻辑为什么是它们而不是更酷的题目1.1 这三道题被放在第一天的真实原因不少人对训练营第一天的印象是“太简单了没什么好学的”我第一遍也是这么想。但二周目重新审视之后我发现这三道题的核心目的不是让你会做而是让你建立几个后续刷题高频使用的思维习惯区间一致性、指针语义、结果数组的构建方式。704 考察的是“在有序结构中快速定位”这是算法题里最基础、出现频率极高的能力。27 考察的是“不借助额外空间原地修改数组”这几乎是所有数组类问题的默认约束。977 则把“有序 平方”这两个条件放在一起诱导你先平方再排序但最优解偏偏是双指针这一下就把“观察数据特征”的能力拉高了。从刷题心理上看第一天放三道相对温和的题也是在帮人建立节奏。我见过太多人一上来就啃动态规划、图论结果几天就放弃了。训练营的策略是先用简单的题目把“写代码的手感”找回来再逐步叠加复杂度。二周目再走这一遍你会明显感觉到自己对“为什么这样做”的理解比第一遍深得多。1.2 三道题在方法论上的递进关系这三道题不是并列关系而是递进关系。704 用到的核心技能是边界控制。你必须明确自己维护的搜索区间是 [left, right] 还是 [left, right)然后每一步都让区间严格收缩否则就会死循环或者漏掉答案。这个能力在后面的二叉搜索树、有序矩阵查找、堆的上下调整里都会反复用到。27 用到的核心技能是双指针。这里的双指针不是那种花哨的快慢指针优化而是“一个指针负责遍历原数组另一个指针负责记录新数组的写入位置”。很多人在做“原地操作”类题目时不知道怎么写原因就是没有建立“快慢指针各司其职”的模型。后面遇到移动零、压缩字符串、链表去重本质都是同一套东西。977 把双指针再推进一步不再是一快一慢而是一左一右向中间夹逼。能使用这种双指针的前提是你要能判断出答案的大致分布规律。平方之后数组的分布是“两端大、中间小”所以从两端拿更大的元素填入结果数组的尾部天然有序。这个“观察单调性”的思路会直接迁移到三数之和、盛水最多的容器、接雨水等题目里。换句话说第一天的三道题就是从“维护区间”到“套用双指针模型”再到“根据数据特征设计指针移动规则”的完整梯度。把这个梯度吃透后面很多题你就会有“这题我见过”的熟悉感。2. 704. 二分查找边界条件才是全部2.1 二分查找的适用前提有序 可随机访问二分查找不是什么高深算法但适用前提必须记清楚数组必须有序并且支持随机访问。这里说的“有序”包括非递减排列如果有重复元素那么查找某个确定值还能做但要找左边界或右边界就得在细节上额外处理。训练营第一天不涉及重复元素的情况先把最基本的模型打牢。随机访问这个条件经常被忽略。链表虽然可能有序但你没法直接用 mid (left right) / 2 跳到中间节点时间复杂度就不再是 O(log n)。所以看到“有序数组”这四个字第一反应就应该是能不能二分如果可以接下来就只需要回答一个问题我维护的区间是左闭右闭还是左闭右开2.2 左闭右闭与左闭右开两种区间的定义差异这是二分查找最容易翻车的地方。我第一遍刷的时候经常写完 while 条件之后不知道 right mid - 1 还是 right mid其实是把区间定义搞混了。先看左闭右闭记为 [left, right]。这种写法表示 left 和 right 都可能在下一轮被检查到。所以 while 循环的条件必须是 left right因为当 left right 时当前这个位置还没有被检查过不能跳过。此时如果 nums[mid] target说明 target 在左半部分新的右边界应该收缩到 mid - 1因为 mid 已经确认不是 target同理nums[mid] target 时left mid 1。再看左闭右开记为 [left, right)。这种写法表示 right 不包含在搜索区间内循环条件必须写成 left right。因为当 left right 时区间为空不需要再循环。此时如果 nums[mid] target新的右边界可以设置为 mid因为 mid 虽然不查但它作为开区间边界是合理的如果 nums[mid] target则 left mid 1。我用一个生活类比来理解左闭右闭像“你把一本书的两页都翻开检查”所以左右页都有可能还没看检查完一页之后就要翻过这一页左闭右开像“左手按住当前页右手只表示翻到的最新一页的下一页”右手指的位置本身永远不看。2.3 二分查找的标准代码模板我二周目用的参照模板是左闭右闭版本因为它在理解上更符合直觉后面改造成查找左右边界也方便。int binarySearch(vectorint nums, int target) { int left 0; int right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { right mid - 1; } else { left mid 1; } } return -1; }注意 mid 的写法。我见过很多人写 (left right) / 2这在多数情况下没问题但当 left 和 right 都接近一个较大值比如 left 10^9right 10^9二者相加就可能溢出 int 的范围。left (right - left) / 2 看起来多写了一点代码但这是专业习惯面试和笔试里都应该这么写。2.4 死循环、越界和漏查的排查方法二分查找的 bug 往往不体现在“结果错得离谱”而体现在“某些测试用例下死循环”或者“边界值查不到”。排查死循环最简单的方法是找两个相邻的例子手动模拟。比如你写的是左闭右开但 while 条件用了 left right并且 right mid那么当 left 和 right 相差 1 的时候mid 等于 left如果 nums[mid] targetleft 变为 mid 1这时候 left 可能直接越过 right但因为你用了 还会继续进入循环最后可能出现 right left 的情况导致越界访问。排查漏查最常见的错误是某次收缩边界时把正确答案也排除了。比如在左闭右闭里写 right mid会导致 mid 位置在下一轮还会被检查虽然不一定会漏掉答案但会让代码逻辑变得不一致。更严重的错误是在左闭右开里写 right mid - 1这会把 mid - 1 和 mid 之间的元素漏掉。我把这两个版本的区分做成了一张表每次写之前看一眼区间定义while 条件收缩方式初始值左闭右闭 [left, right]left rightright mid - 1left mid 1right size - 1左闭右开 [left, right)left rightright midleft mid 1right size提示不管选哪种写法整个循环体内部必须始终遵守同一个区间定义。这就是常说的“循环不变量”。只要有人问你二分查找的坑答案永远指向循环不变量是否被破坏。3. 27. 移除元素快慢双指针的第一次亮相3.1 为什么不能直接用库函数 remove这道题要求返回移除指定值后的新长度同时要求原地修改。很多人第一反应是调用编程语言自带的 remove 函数比如 C 的 std::remove 或者 Python 的列表推导但题目明确要求“不要使用额外的数组空间必须仅使用 O(1) 额外内存并原地修改输入数组”。就算你硬用库函数比如 C 的 std::remove它底层其实也是双指针实现的只是把逻辑封装了起来。这违背了刷题练手的目的。更关键的是很多面试官会追问你 remove 内部怎么做、时间空间复杂度多少如果你只回答“库函数给我处理了”这一轮基本就凉了。刷题训练营第一天安排这道题就是让你亲手把 remove 的底层逻辑写一遍。3.2 快慢指针的移动规则快慢指针的核心思想是快指针负责遍历原数组慢指针负责指向结果数组中下一个要写入的位置。初始时fast 和 slow 都指向下标 0。fast 每轮往前走一步检查当前元素是否等于 val。如果不等于 val说明这个元素应该保留就把它写到 nums[slow] 的位置然后 slow 加一。如果等于 val说明这个元素要被移除直接跳过slow 不动fast 继续前进。这样做的效果是所有不等于 val 的元素都会被依次复制到数组的前面slow 每加一次就相当于结果数组的有效长度加一。最终 slow 的值就是移除所有目标值之后的新长度。需要注意这个过程不是删除操作而是覆盖操作。原数组中 slow 之后的位置可能还残留一些旧值但题目只要求返回新长度后边的元素是什么无所谓LeetCode 的测试用例也只检查新长度范围内的内容。3.3 代码实现与手动模拟int removeElement(vectorint nums, int val) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; slow; } } return slow; }拿 k3 体验一下。设 nums [3,2,2,3]val 3。fast 0nums[0] 3跳过slow 0。fast 1nums[1] 2执行 nums[0] 2slow 1。fast 2nums[2] 2执行 nums[1] 2slow 2。fast 3nums[3] 3跳过。返回 slow 2nums 的前两位是 [2,2]。整个过程只遍历一遍时间复杂度 O(n)空间复杂度 O(1)。这里还有一个隐藏知识点为什么覆盖而不是交换交换也能实现移除但会把不需要的元素挪到后面最后返回的 slow 长度不变。但如果要求结果数组中元素的相对顺序保持不变覆盖就是最稳妥的方案。快慢双指针天然保证相对顺序因为 fast 是按顺序遍历的。3.4 变体与应用场景移除元素这道题最典型的变体是“移动零”。给定数组把所有的 0 移动到末尾同时保持非零元素的相对顺序。解法几乎一样只是把“不等于 val”换成“不等于 0”最后再把 slow 之后的元素全部置成 0。另一个变体是“删除有序数组中的重复项”。这个题要求原地删除重复元素返回新长度。它需要 fast 指针跳过所有和 slow 位置相同的元素本质上还是快慢指针的思想只不过比较的是两个指针所指的元素值。我在二周目做这些变体时最大的感受是只要把“快指针负责探索慢指针负责记录”这个模型刻进脑子这类题目根本不需要背代码临时推都能推出来。注意快慢指针不总是从左到右。有些题目需要从两端同时开始比如后续的盛水容器。判断用哪种双指针模型关键看题目条件里是否存在“两端大中间小”“两端和”这类特征。4. 977. 有序数组的平方从两端向中间逼近的智慧4.1 直接平方后排序的问题所在这道题输入是非递减数组可能有负数比如 [-4, -1, 0, 3, 10]。最直接的做法是把每个数平方然后直接 sort代码确实很短vectorint sortedSquares(vectorint nums) { vectorint res(nums.size(), 0); for (int i 0; i nums.size(); i) { res[i] nums[i] * nums[i]; } sort(res.begin(), res.end()); return res; }这个解法不是完全不行时间复杂度是 O(n log n)在 LeetCode 上也能通过。但训练营的第一天就强调“先想清楚再写代码”这道题隐藏的条件是原始数组已经有序只是负数的平方会破坏有序性。既然有序性被破坏得有规律我们就可以利用这个规律把时间复杂度降到 O(n)。4.2 为什么最大值只会出现在两端对于非递减数组平方后的情况可以分成三段考虑负数部分、0如果有、正数部分。负数平方之后是递减的比如 [-4, -1] 平方后变成 [16, 1]越靠左的负数平方越大正数部分平方后仍然是递增的比如 [3, 10] 平方后变成 [9, 100]。所以整个数组平方后的全局最大值一定出现在原数组的左端或者右端不可能出现在中间。因为中间的数绝对值小。同理全局次大值一定出现在除掉刚才那个最大值之后的新的左端或右端。这是典型的“两端大中间小”的分布。只要抓住这一点就可以从两端同时往中间走每次选出更大的那个平方值从结果数组的末尾开始向前填入。4.3 双指针代码实现与细节处理vectorint sortedSquares(vectorint nums) { int n nums.size(); vectorint res(n, 0); int left 0; int right n - 1; int k n - 1; while (left right) { int leftSquare nums[left] * nums[left]; int rightSquare nums[right] * nums[right]; if (leftSquare rightSquare) { res[k--] leftSquare; left; } else { res[k--] rightSquare; right--; } } return res; }代码里有几个值得注意的细节第一res 数组的长度必须预先声明为 n否则直接 push_back 的话顺序会错乱。因为我们是从结果数组的末尾往前填如果每次都 push_back整个顺序就反了。第二while 循环的结束条件是 left right。当 left 和 right 指向同一个元素时这个元素还没有被处理过必须再执行一轮把它放入结果数组所以不能写成 left right。第三比较平方值时我建议用 long long 承接或者至少确定数组元素范围不会导致 int 溢出。训练营的测试用例一般比较温和但面试中如果 nums[i] 是 10^4平方就是 10^8再加几个数量级就危险了。稳妥做法long long leftSquare 1LL * nums[left] * nums[left]; long long rightSquare 1LL * nums[right] * nums[right];4.4 与前面两题的方法论呼应这道题和 27 题都用了双指针但移动策略完全不同。27 题的快慢指针是从同一起点出发一个快一个慢977 题是两端向中间逼近。为什么会有这个差异因为 27 题只看一个方向上的“保留还是跳过”而 977 题必须同时考虑两个方向的优先级。这种“根据数据分布设计双指针移动规则”的能力恰好是第一天的总结。后面你会在很多题目里看到同样的套路三数之和用左右指针扫描盛水容器用左右指针收缩接雨水虽然复杂一点本质上也是从两端向中间记录峰值。二刷的时候我给自己提了一个问题如果题目改成“有序数组的立方”还能不能用双指针仔细想想会发现不行因为正负数的三次方单调性完全被打乱了最大值可能出现在中间。这就是“观察到规律再决定用不用双指针”的典型案例。5. 常见问题与排查技巧实录5.1 二分查找的四个高频错误我在二刷的时候把以前提交过的错误版本翻出来看了一遍发现错误类型非常集中。第一个错误是 while 条件写错。用了左闭右闭的收缩方式却写了 left right导致当 left right 时循环结束漏查最后一个元素。第二个错误是 right 的收缩写错。在左闭右闭里直接写 right mid把已经检查过的 mid 又放进下一轮区间虽然多数情况下不致死循环但会让“循环不变量”失效排查起来很痛苦。第三个错误是 mid 计算溢出。写成 mid (left right) / 2如果 left 和 right 都很大可能溢出。解决方案就是 left (right - left) / 2。第四个错误是忘记考虑数组为空的情况。如果 nums.size() 0初始 right -1这时候 while (left right) 会直接跳过返回 -1倒是没问题。但如果你初始 right nums.size()应该用左闭右开版本否则就越界了。5.2 移除元素的不明显陷阱移除元素的代码很短但有个陷阱出现在“返回长度”上。很多人把 slow 和 fast 搞混最后返回 fast 而不是 slow。fast 是遍历完整个数组的终值等于原数组长度不是新长度。new length 应该是慢指针 slow 的值。另一个陷阱是覆盖时写反。我见过有人写nums[fast] nums[slow];这完全反了。fast 是探索者slow 是接收者必须把 fast 指向的值往 slow 位置搬而不是相反。还有一个不明显的坑如果输入数组全是 val比如 nums [3,3], val 3那么循环里 fast 走完slow 一直为 0返回 0。这是正确的。但有人会把 slow 初始化为 1或者循环结束后 slow导致多返回一个长度面试时很容易被追问考倒。5.3 有序数组平方的常见失分点这道题最容易失分的点不是算法而是结果数组的顺序。如果你从左往右填充结果数组必须把较小值放在前面但双指针比较的是较大值从前往后填充会非常别扭。我见过一个版本的代码把较大值往前填结果整个数组的顺序完全乱了测试用例直接失败。还有一个问题是循环结束后忘记把剩下的元素放入结果数组。使用 while (left right) 这个写法循环退出时所有元素都已经处理完不需要补丁。但如果写的是 while (left right)中间剩下的那个元素就漏掉了需要在循环外再补一次。容易忽视的点正确做法出错后果res 数组预分配vector res(n, 0)push_back 导致顺序颠倒leftSquare 溢出用 long long 承接结果错误循环条件left right中间元素漏处理平方值重复计算先存入变量代码冗余不易排查5.4 一套可复用的自查清单二刷第一天我在本子上写了一组自查问题后面每做一道数组题都会过一遍我用到的指针指向哪个语义快指针探索、慢指针记录还是左右夹逼每次移动之后区间或指针关系是否还满足“整个过程不变量”循环退出后是否还有元素没处理完如果有循环条件为什么要这样写结果数组的填充方向是前到后还是后到前填充下标是增加还是减少是否有整数溢出的风险乘法、加法之前先估算一下数据范围。这套清单看起来基础但确实能救场。我二周目做这些题的时候有好几次写完代码觉得没问题一跑测试用例发现边界状况不对最后都是靠清单里的某一条定位出来的。6. 二周目的复盘策略与我个人的体会6.1 二刷时关注的维度应该是什么二刷的目的不是“再做一遍”而是“换一个视角看题目”。第一遍刷我通常只关注“怎么写能通过”所以代码写得很机械边界情况全靠试错。二刷我强制自己先写清楚三个东西题目给的核心条件、能用的数据结构限制、最优解背后利用了哪个性质。比如二分查找一刷我会背 while 条件二刷我会先写出区间定义再推 while 条件。移除元素一刷我会背快慢指针模板二刷我会想清楚为什么这样用可以不改变元素相对顺序。有序数组的平方一刷我会记住两端夹逼二刷我会画出平方后的分布才真正理解为什么最大值在两端。建议后面入坑训练营的同学第一遍不要太纠结正确率先保证每道题的思路能看懂、代码能写出来。但到了二周目必须强迫自己把“为什么”讲出来哪怕对着空气讲也行。我亲身测试过能口头讲清楚一道题远比能默写代码重要得多。6.2 第一天常见的心理误区与调整方法二刷过程中我发现一个很普遍的心理误区觉得题目简单就跳着刷或者只做自己擅长的题。第一天看起来容易但如果你直接略过后面碰到“搜索插入位置”“删除有序数组重复项”“合并两个有序数组”的时候就会发现自己对区间和指针的理解并不牢。调整方法是给自己设置一个“最小复习单元”不要求一天刷很多题但要求把每一道题的边界条件、时间空间复杂度、对应模板的变化方式都写下来。第一天就三题完全有充足时间去抠细节。我二刷时给每道题都写了两个版本比如二分查找分别用左闭右闭和左闭右开实现移除元素分别用快慢指针和两端交换实现然后对比两者在不同测试数据下的表现差异。6.3 踩过几次坑之后总结出的第一天行动清单先用 20 分钟自己思考再去看题解。二刷时即使有印象也要逼自己先写一遍。每道题至少写两个版本。比如二分查找写左闭右闭和左闭右开移除元素写覆盖法和交换法平方题写暴力 sort 法和双指针法。用几个极端测试数据检查代码空数组、单元素数组、全相等数组、全等于目标值数组、最大负数与最大正数的组合。把三道题放进一个笔记里分别标注“核心条件”“解法思路”“常见错误”“变体方向”。当天晚上再用五分钟口头复述每道题的思路如果卡壳第二天早上立刻重新写一遍。我个人的体会是第一天的心态决定了整个训练营的节奏。你如果觉得三道题简单到不需要复盘那么在后面遇到二维数组、链表、二叉树时大概率会因为基础动作不熟练而反复卡壳。反过来如果你能在第一天就把边界、指针、不变量这些东西练成肌肉记忆后续刷中等题和难题时至少能把精力集中在“新思路”而不是“基础实现”上。最后再分享一个小技巧这三道题里二分查找最值得一题多解。如果你能把左闭右闭、左闭右开、递归版本、迭代版本都写一遍并且能解释清楚每个版本里 mid 和边界收缩的变化那你对区间的理解基本就过关了。后面的题目哪怕再复杂也都是在这些基础动作上叠加新的想法。第一天把地基打牢后面才能吃得下更硬的菜。 
长河君 · 2026/10/11 4:33:17 · 阅读 1.2k 二刷算法第一天：二分查找与双指针的底层思维拆解
标题里的“吃饭香”不是夸张是我这段时间重刷算法题的真实状态。第一次过 704、27、977 这三道题的时候我基本处于“抄一遍代码第二天就忘”的阶段边界条件稍微一改就全乱。到了二周目重新打开它们才意识到这套训练营把这三道题放在第一天根本不是随便凑数的704二分查找逼你把区间定义想清楚27移除元素带出快慢双指针这个基础范式977有序数组的平方又把双指针扩展成两端夹逼。三道题单独看都简单合在一起却覆盖了后面大部分题目的底层动作。这篇文章就是我在二周目第一天的完整记录包含每道题的思路拆解、可复制的代码模板、常见 bug 清单以及我在实际刷题过程中踩过的坑。适合刚入门算法、准备系统刷题或者正在二刷三刷的朋友参考。1. 第一天三道题的设计逻辑为什么是它们而不是更酷的题目1.1 这三道题被放在第一天的真实原因不少人对训练营第一天的印象是“太简单了没什么好学的”我第一遍也是这么想。但二周目重新审视之后我发现这三道题的核心目的不是让你会做而是让你建立几个后续刷题高频使用的思维习惯区间一致性、指针语义、结果数组的构建方式。704 考察的是“在有序结构中快速定位”这是算法题里最基础、出现频率极高的能力。27 考察的是“不借助额外空间原地修改数组”这几乎是所有数组类问题的默认约束。977 则把“有序 平方”这两个条件放在一起诱导你先平方再排序但最优解偏偏是双指针这一下就把“观察数据特征”的能力拉高了。从刷题心理上看第一天放三道相对温和的题也是在帮人建立节奏。我见过太多人一上来就啃动态规划、图论结果几天就放弃了。训练营的策略是先用简单的题目把“写代码的手感”找回来再逐步叠加复杂度。二周目再走这一遍你会明显感觉到自己对“为什么这样做”的理解比第一遍深得多。1.2 三道题在方法论上的递进关系这三道题不是并列关系而是递进关系。704 用到的核心技能是边界控制。你必须明确自己维护的搜索区间是 [left, right] 还是 [left, right)然后每一步都让区间严格收缩否则就会死循环或者漏掉答案。这个能力在后面的二叉搜索树、有序矩阵查找、堆的上下调整里都会反复用到。27 用到的核心技能是双指针。这里的双指针不是那种花哨的快慢指针优化而是“一个指针负责遍历原数组另一个指针负责记录新数组的写入位置”。很多人在做“原地操作”类题目时不知道怎么写原因就是没有建立“快慢指针各司其职”的模型。后面遇到移动零、压缩字符串、链表去重本质都是同一套东西。977 把双指针再推进一步不再是一快一慢而是一左一右向中间夹逼。能使用这种双指针的前提是你要能判断出答案的大致分布规律。平方之后数组的分布是“两端大、中间小”所以从两端拿更大的元素填入结果数组的尾部天然有序。这个“观察单调性”的思路会直接迁移到三数之和、盛水最多的容器、接雨水等题目里。换句话说第一天的三道题就是从“维护区间”到“套用双指针模型”再到“根据数据特征设计指针移动规则”的完整梯度。把这个梯度吃透后面很多题你就会有“这题我见过”的熟悉感。2. 704. 二分查找边界条件才是全部2.1 二分查找的适用前提有序 可随机访问二分查找不是什么高深算法但适用前提必须记清楚数组必须有序并且支持随机访问。这里说的“有序”包括非递减排列如果有重复元素那么查找某个确定值还能做但要找左边界或右边界就得在细节上额外处理。训练营第一天不涉及重复元素的情况先把最基本的模型打牢。随机访问这个条件经常被忽略。链表虽然可能有序但你没法直接用 mid (left right) / 2 跳到中间节点时间复杂度就不再是 O(log n)。所以看到“有序数组”这四个字第一反应就应该是能不能二分如果可以接下来就只需要回答一个问题我维护的区间是左闭右闭还是左闭右开2.2 左闭右闭与左闭右开两种区间的定义差异这是二分查找最容易翻车的地方。我第一遍刷的时候经常写完 while 条件之后不知道 right mid - 1 还是 right mid其实是把区间定义搞混了。先看左闭右闭记为 [left, right]。这种写法表示 left 和 right 都可能在下一轮被检查到。所以 while 循环的条件必须是 left right因为当 left right 时当前这个位置还没有被检查过不能跳过。此时如果 nums[mid] target说明 target 在左半部分新的右边界应该收缩到 mid - 1因为 mid 已经确认不是 target同理nums[mid] target 时left mid 1。再看左闭右开记为 [left, right)。这种写法表示 right 不包含在搜索区间内循环条件必须写成 left right。因为当 left right 时区间为空不需要再循环。此时如果 nums[mid] target新的右边界可以设置为 mid因为 mid 虽然不查但它作为开区间边界是合理的如果 nums[mid] target则 left mid 1。我用一个生活类比来理解左闭右闭像“你把一本书的两页都翻开检查”所以左右页都有可能还没看检查完一页之后就要翻过这一页左闭右开像“左手按住当前页右手只表示翻到的最新一页的下一页”右手指的位置本身永远不看。2.3 二分查找的标准代码模板我二周目用的参照模板是左闭右闭版本因为它在理解上更符合直觉后面改造成查找左右边界也方便。int binarySearch(vectorint nums, int target) { int left 0; int right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { right mid - 1; } else { left mid 1; } } return -1; }注意 mid 的写法。我见过很多人写 (left right) / 2这在多数情况下没问题但当 left 和 right 都接近一个较大值比如 left 10^9right 10^9二者相加就可能溢出 int 的范围。left (right - left) / 2 看起来多写了一点代码但这是专业习惯面试和笔试里都应该这么写。2.4 死循环、越界和漏查的排查方法二分查找的 bug 往往不体现在“结果错得离谱”而体现在“某些测试用例下死循环”或者“边界值查不到”。排查死循环最简单的方法是找两个相邻的例子手动模拟。比如你写的是左闭右开但 while 条件用了 left right并且 right mid那么当 left 和 right 相差 1 的时候mid 等于 left如果 nums[mid] targetleft 变为 mid 1这时候 left 可能直接越过 right但因为你用了 还会继续进入循环最后可能出现 right left 的情况导致越界访问。排查漏查最常见的错误是某次收缩边界时把正确答案也排除了。比如在左闭右闭里写 right mid会导致 mid 位置在下一轮还会被检查虽然不一定会漏掉答案但会让代码逻辑变得不一致。更严重的错误是在左闭右开里写 right mid - 1这会把 mid - 1 和 mid 之间的元素漏掉。我把这两个版本的区分做成了一张表每次写之前看一眼区间定义while 条件收缩方式初始值左闭右闭 [left, right]left rightright mid - 1left mid 1right size - 1左闭右开 [left, right)left rightright midleft mid 1right size提示不管选哪种写法整个循环体内部必须始终遵守同一个区间定义。这就是常说的“循环不变量”。只要有人问你二分查找的坑答案永远指向循环不变量是否被破坏。3. 27. 移除元素快慢双指针的第一次亮相3.1 为什么不能直接用库函数 remove这道题要求返回移除指定值后的新长度同时要求原地修改。很多人第一反应是调用编程语言自带的 remove 函数比如 C 的 std::remove 或者 Python 的列表推导但题目明确要求“不要使用额外的数组空间必须仅使用 O(1) 额外内存并原地修改输入数组”。就算你硬用库函数比如 C 的 std::remove它底层其实也是双指针实现的只是把逻辑封装了起来。这违背了刷题练手的目的。更关键的是很多面试官会追问你 remove 内部怎么做、时间空间复杂度多少如果你只回答“库函数给我处理了”这一轮基本就凉了。刷题训练营第一天安排这道题就是让你亲手把 remove 的底层逻辑写一遍。3.2 快慢指针的移动规则快慢指针的核心思想是快指针负责遍历原数组慢指针负责指向结果数组中下一个要写入的位置。初始时fast 和 slow 都指向下标 0。fast 每轮往前走一步检查当前元素是否等于 val。如果不等于 val说明这个元素应该保留就把它写到 nums[slow] 的位置然后 slow 加一。如果等于 val说明这个元素要被移除直接跳过slow 不动fast 继续前进。这样做的效果是所有不等于 val 的元素都会被依次复制到数组的前面slow 每加一次就相当于结果数组的有效长度加一。最终 slow 的值就是移除所有目标值之后的新长度。需要注意这个过程不是删除操作而是覆盖操作。原数组中 slow 之后的位置可能还残留一些旧值但题目只要求返回新长度后边的元素是什么无所谓LeetCode 的测试用例也只检查新长度范围内的内容。3.3 代码实现与手动模拟int removeElement(vectorint nums, int val) { int slow 0; for (int fast 0; fast nums.size(); fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; slow; } } return slow; }拿 k3 体验一下。设 nums [3,2,2,3]val 3。fast 0nums[0] 3跳过slow 0。fast 1nums[1] 2执行 nums[0] 2slow 1。fast 2nums[2] 2执行 nums[1] 2slow 2。fast 3nums[3] 3跳过。返回 slow 2nums 的前两位是 [2,2]。整个过程只遍历一遍时间复杂度 O(n)空间复杂度 O(1)。这里还有一个隐藏知识点为什么覆盖而不是交换交换也能实现移除但会把不需要的元素挪到后面最后返回的 slow 长度不变。但如果要求结果数组中元素的相对顺序保持不变覆盖就是最稳妥的方案。快慢双指针天然保证相对顺序因为 fast 是按顺序遍历的。3.4 变体与应用场景移除元素这道题最典型的变体是“移动零”。给定数组把所有的 0 移动到末尾同时保持非零元素的相对顺序。解法几乎一样只是把“不等于 val”换成“不等于 0”最后再把 slow 之后的元素全部置成 0。另一个变体是“删除有序数组中的重复项”。这个题要求原地删除重复元素返回新长度。它需要 fast 指针跳过所有和 slow 位置相同的元素本质上还是快慢指针的思想只不过比较的是两个指针所指的元素值。我在二周目做这些变体时最大的感受是只要把“快指针负责探索慢指针负责记录”这个模型刻进脑子这类题目根本不需要背代码临时推都能推出来。注意快慢指针不总是从左到右。有些题目需要从两端同时开始比如后续的盛水容器。判断用哪种双指针模型关键看题目条件里是否存在“两端大中间小”“两端和”这类特征。4. 977. 有序数组的平方从两端向中间逼近的智慧4.1 直接平方后排序的问题所在这道题输入是非递减数组可能有负数比如 [-4, -1, 0, 3, 10]。最直接的做法是把每个数平方然后直接 sort代码确实很短vectorint sortedSquares(vectorint nums) { vectorint res(nums.size(), 0); for (int i 0; i nums.size(); i) { res[i] nums[i] * nums[i]; } sort(res.begin(), res.end()); return res; }这个解法不是完全不行时间复杂度是 O(n log n)在 LeetCode 上也能通过。但训练营的第一天就强调“先想清楚再写代码”这道题隐藏的条件是原始数组已经有序只是负数的平方会破坏有序性。既然有序性被破坏得有规律我们就可以利用这个规律把时间复杂度降到 O(n)。4.2 为什么最大值只会出现在两端对于非递减数组平方后的情况可以分成三段考虑负数部分、0如果有、正数部分。负数平方之后是递减的比如 [-4, -1] 平方后变成 [16, 1]越靠左的负数平方越大正数部分平方后仍然是递增的比如 [3, 10] 平方后变成 [9, 100]。所以整个数组平方后的全局最大值一定出现在原数组的左端或者右端不可能出现在中间。因为中间的数绝对值小。同理全局次大值一定出现在除掉刚才那个最大值之后的新的左端或右端。这是典型的“两端大中间小”的分布。只要抓住这一点就可以从两端同时往中间走每次选出更大的那个平方值从结果数组的末尾开始向前填入。4.3 双指针代码实现与细节处理vectorint sortedSquares(vectorint nums) { int n nums.size(); vectorint res(n, 0); int left 0; int right n - 1; int k n - 1; while (left right) { int leftSquare nums[left] * nums[left]; int rightSquare nums[right] * nums[right]; if (leftSquare rightSquare) { res[k--] leftSquare; left; } else { res[k--] rightSquare; right--; } } return res; }代码里有几个值得注意的细节第一res 数组的长度必须预先声明为 n否则直接 push_back 的话顺序会错乱。因为我们是从结果数组的末尾往前填如果每次都 push_back整个顺序就反了。第二while 循环的结束条件是 left right。当 left 和 right 指向同一个元素时这个元素还没有被处理过必须再执行一轮把它放入结果数组所以不能写成 left right。第三比较平方值时我建议用 long long 承接或者至少确定数组元素范围不会导致 int 溢出。训练营的测试用例一般比较温和但面试中如果 nums[i] 是 10^4平方就是 10^8再加几个数量级就危险了。稳妥做法long long leftSquare 1LL * nums[left] * nums[left]; long long rightSquare 1LL * nums[right] * nums[right];4.4 与前面两题的方法论呼应这道题和 27 题都用了双指针但移动策略完全不同。27 题的快慢指针是从同一起点出发一个快一个慢977 题是两端向中间逼近。为什么会有这个差异因为 27 题只看一个方向上的“保留还是跳过”而 977 题必须同时考虑两个方向的优先级。这种“根据数据分布设计双指针移动规则”的能力恰好是第一天的总结。后面你会在很多题目里看到同样的套路三数之和用左右指针扫描盛水容器用左右指针收缩接雨水虽然复杂一点本质上也是从两端向中间记录峰值。二刷的时候我给自己提了一个问题如果题目改成“有序数组的立方”还能不能用双指针仔细想想会发现不行因为正负数的三次方单调性完全被打乱了最大值可能出现在中间。这就是“观察到规律再决定用不用双指针”的典型案例。5. 常见问题与排查技巧实录5.1 二分查找的四个高频错误我在二刷的时候把以前提交过的错误版本翻出来看了一遍发现错误类型非常集中。第一个错误是 while 条件写错。用了左闭右闭的收缩方式却写了 left right导致当 left right 时循环结束漏查最后一个元素。第二个错误是 right 的收缩写错。在左闭右闭里直接写 right mid把已经检查过的 mid 又放进下一轮区间虽然多数情况下不致死循环但会让“循环不变量”失效排查起来很痛苦。第三个错误是 mid 计算溢出。写成 mid (left right) / 2如果 left 和 right 都很大可能溢出。解决方案就是 left (right - left) / 2。第四个错误是忘记考虑数组为空的情况。如果 nums.size() 0初始 right -1这时候 while (left right) 会直接跳过返回 -1倒是没问题。但如果你初始 right nums.size()应该用左闭右开版本否则就越界了。5.2 移除元素的不明显陷阱移除元素的代码很短但有个陷阱出现在“返回长度”上。很多人把 slow 和 fast 搞混最后返回 fast 而不是 slow。fast 是遍历完整个数组的终值等于原数组长度不是新长度。new length 应该是慢指针 slow 的值。另一个陷阱是覆盖时写反。我见过有人写nums[fast] nums[slow];这完全反了。fast 是探索者slow 是接收者必须把 fast 指向的值往 slow 位置搬而不是相反。还有一个不明显的坑如果输入数组全是 val比如 nums [3,3], val 3那么循环里 fast 走完slow 一直为 0返回 0。这是正确的。但有人会把 slow 初始化为 1或者循环结束后 slow导致多返回一个长度面试时很容易被追问考倒。5.3 有序数组平方的常见失分点这道题最容易失分的点不是算法而是结果数组的顺序。如果你从左往右填充结果数组必须把较小值放在前面但双指针比较的是较大值从前往后填充会非常别扭。我见过一个版本的代码把较大值往前填结果整个数组的顺序完全乱了测试用例直接失败。还有一个问题是循环结束后忘记把剩下的元素放入结果数组。使用 while (left right) 这个写法循环退出时所有元素都已经处理完不需要补丁。但如果写的是 while (left right)中间剩下的那个元素就漏掉了需要在循环外再补一次。容易忽视的点正确做法出错后果res 数组预分配vector res(n, 0)push_back 导致顺序颠倒leftSquare 溢出用 long long 承接结果错误循环条件left right中间元素漏处理平方值重复计算先存入变量代码冗余不易排查5.4 一套可复用的自查清单二刷第一天我在本子上写了一组自查问题后面每做一道数组题都会过一遍我用到的指针指向哪个语义快指针探索、慢指针记录还是左右夹逼每次移动之后区间或指针关系是否还满足“整个过程不变量”循环退出后是否还有元素没处理完如果有循环条件为什么要这样写结果数组的填充方向是前到后还是后到前填充下标是增加还是减少是否有整数溢出的风险乘法、加法之前先估算一下数据范围。这套清单看起来基础但确实能救场。我二周目做这些题的时候有好几次写完代码觉得没问题一跑测试用例发现边界状况不对最后都是靠清单里的某一条定位出来的。6. 二周目的复盘策略与我个人的体会6.1 二刷时关注的维度应该是什么二刷的目的不是“再做一遍”而是“换一个视角看题目”。第一遍刷我通常只关注“怎么写能通过”所以代码写得很机械边界情况全靠试错。二刷我强制自己先写清楚三个东西题目给的核心条件、能用的数据结构限制、最优解背后利用了哪个性质。比如二分查找一刷我会背 while 条件二刷我会先写出区间定义再推 while 条件。移除元素一刷我会背快慢指针模板二刷我会想清楚为什么这样用可以不改变元素相对顺序。有序数组的平方一刷我会记住两端夹逼二刷我会画出平方后的分布才真正理解为什么最大值在两端。建议后面入坑训练营的同学第一遍不要太纠结正确率先保证每道题的思路能看懂、代码能写出来。但到了二周目必须强迫自己把“为什么”讲出来哪怕对着空气讲也行。我亲身测试过能口头讲清楚一道题远比能默写代码重要得多。6.2 第一天常见的心理误区与调整方法二刷过程中我发现一个很普遍的心理误区觉得题目简单就跳着刷或者只做自己擅长的题。第一天看起来容易但如果你直接略过后面碰到“搜索插入位置”“删除有序数组重复项”“合并两个有序数组”的时候就会发现自己对区间和指针的理解并不牢。调整方法是给自己设置一个“最小复习单元”不要求一天刷很多题但要求把每一道题的边界条件、时间空间复杂度、对应模板的变化方式都写下来。第一天就三题完全有充足时间去抠细节。我二刷时给每道题都写了两个版本比如二分查找分别用左闭右闭和左闭右开实现移除元素分别用快慢指针和两端交换实现然后对比两者在不同测试数据下的表现差异。6.3 踩过几次坑之后总结出的第一天行动清单先用 20 分钟自己思考再去看题解。二刷时即使有印象也要逼自己先写一遍。每道题至少写两个版本。比如二分查找写左闭右闭和左闭右开移除元素写覆盖法和交换法平方题写暴力 sort 法和双指针法。用几个极端测试数据检查代码空数组、单元素数组、全相等数组、全等于目标值数组、最大负数与最大正数的组合。把三道题放进一个笔记里分别标注“核心条件”“解法思路”“常见错误”“变体方向”。当天晚上再用五分钟口头复述每道题的思路如果卡壳第二天早上立刻重新写一遍。我个人的体会是第一天的心态决定了整个训练营的节奏。你如果觉得三道题简单到不需要复盘那么在后面遇到二维数组、链表、二叉树时大概率会因为基础动作不熟练而反复卡壳。反过来如果你能在第一天就把边界、指针、不变量这些东西练成肌肉记忆后续刷中等题和难题时至少能把精力集中在“新思路”而不是“基础实现”上。最后再分享一个小技巧这三道题里二分查找最值得一题多解。如果你能把左闭右闭、左闭右开、递归版本、迭代版本都写一遍并且能解释清楚每个版本里 mid 和边界收缩的变化那你对区间的理解基本就过关了。后面的题目哪怕再复杂也都是在这些基础动作上叠加新的想法。第一天把地基打牢后面才能吃得下更硬的菜。