1. 三个题目放在一起其实是同一条主线第一天打卡三题连刷704.二分查找、27.移除元素、977.有序数组的平方。很多第一次接触代码随想录训练营的朋友看到这个组合会有点疑惑前两个题还能理解一个查一个删第三个怎么都是平方了这三个题凑在一起有什么关联实际上这三个题是精心安排的。它们表面上考察的是不同的题目场景内里却在反复训练同一个核心能力——对索引的控制。数组相关的算法题本质上就是围绕索引做文章你要找哪个位置你要删哪些位置你要重新排哪些位置全部落在索引的移动和边界判断上。第一天就用三道看似不同、实际同源的题目把“索引思维”这件事给立住这是我觉得训练营开篇设计最聪明的地方。704考察的是对区间边界的理解一个区间的左端、右端、中点怎么收缩、怎么更新写错一个符号就是死循环27考察的是双指针的配合快指针在前面探路慢指针在后面写位两个索引各司其职977则是双指针的另一种形态从两端往中间走因为平方之后最大值往往藏头尾。三题走下来你对“索引”这个抽象概念会有一个特别具体的体感。所以这篇文章不适合只贴答案我会把每一步的思考链补全包括为什么要这么写、不这么写会踩什么坑、实现时的细节怎么处理。同时我尽可能用工程化一点的口吻来写毕竟算法题不是背模板关键是建立能迁移的思路。如果你正打算跟上训练营节奏或者刚开始刷题想要一套清晰的起步框架这篇可以当作第一天的复习笔记来读。在动手写代码之前我还想先聊一个特别重要的习惯拿到题先别冲代码先问自己三个问题。第一这道题的数据结构是什么尤其是数据是否有序、能否原地修改第二暴力解法长什么样复杂度是多少优化空间在哪里第三边界条件有哪些空数组、单元素、目标不存在、重复元素这些场景下的行为是否经过推演。这套“自己问自己”的流程基本可以覆盖训练营后续大部分题目第一天就把它焊进习惯里后面会省很多力。2. 704.二分查找边界条件定生死2.1 二分的前提条件704.二分查找给的是一个有序数组和一个目标值要求返回目标值的下标找不到就返回-1。为什么强调有序因为只有有序数组才具备“每次丢弃一半数据”的条件这是二分查找能够把时间复杂度压到O(log n)的基础。回想一下一个朴素但准确的记忆方式你在电话簿里找一个姓氏你不会从第一页翻到最后一页你会直接翻到中间根据姓氏的字母范围判断目标在左半本还是右半本然后重复这个过程。这就是二分查找的生活原型。但这里有个容易忽略的问题题目还要求数组中没有重复元素。为什么因为如果存在重复目标值二分查找返回哪个下标就需要额外定义。LC题目如果出现重复元素通常会改成“查找左边界”或“右边界”那又是另一个进阶话题这里先不展开。一句话总结二分框架每次在一个区间内取中点比较中点的值和目标值的大小关系决定收缩左边界还是右边界。核心难点从来不是框架而是边界的开闭约定。2.2 左闭右闭和左闭右开到底差在哪网上的二分模板五花八门归根结底只分两大类左闭右闭区间[left, right]和左闭右开区间[left, right)。两种都能AC但如果你混着写今天写个left right明天写个left right后天把right赋值写成mid就非常容易在细节上翻车。我的建议是选一种自己最顺手的区间定义然后每次写二分都保持同一套逻辑。我个人长期用左闭右闭因为它的语义最直观left和right指向的元素都在有效区间内。用左闭右闭的思路写核心就三件事初始化left 0, right nums.size() - 1。注意right必须是最后一个有效下标不能是size()否则一开始就把数组越界了。循环条件left right。因为左右端点都是有效值当left等于right时区间里还有一个元素必须再查一次。更新逻辑如果nums[mid] target说明目标在左半边此时right mid - 1如果nums[mid] target说明目标在右半边left mid 1。为什么不直接right mid因为我们用的是闭区间mid已经检查过了确定不是目标值就不该再留在区间内。如果换成左闭右开同样的思路则有不同的细节。初始化时right nums.size()原因是右侧是开区间right本身不参与检查循环条件变成left right因为当left等于right时区间已经为空没必要再进循环更新逻辑里right mid因为mid没有被检查右端点可以保留它作为开区间边界而left mid 1。这套逻辑也自洽但你的每个细节都必须保持“右开”的语义。很多初学者第一天就栽在这个上面用了左闭右闭的循环条件却用左闭右开的更新逻辑最后跳不出循环。理解区间的“不变量”是二分真正的门槛也就是“我当前维护的区间到底是什么含义、是否还有未被排除的元素”。写法初始化循环条件中点更新是否检查中点左闭右闭left0, rightlen-1left rightleft mid1 / right mid-1mid已被排除左闭右开left0, rightlenleft rightleft mid1 / right midmid可作为边界保留2.3 中点计算别小看left (right - left) / 2很多教程一上来就写int mid (left right) / 2这个写法在数学上没问题但在工程上有隐患。当left和right都非常大时比如接近int上限两者相加可能溢出整型范围这在生产环境或者面试官的刻意追问下都是减分项。推荐的写法是int mid left (right - left) / 2。这个式子是先用right - left得到区间长度再除以2最后加上left本质上算的还是中间位置但保证每一步的值都在安全范围内。你可以把它理解成量一段距离的两种方式一是直接量总长度再均分二是在起点基础上再加半段。第二种明显更稳因为只涉及小数值的运算。这行代码虽然只有一行但在面试或者实际工程实现里它是一个很好的“代码敏感度”信号。建议第一天就刻进肌肉记忆后面所有需要二分的题目都用这种写法。3.3 死循环、找错边界、漏掉目标再好的模板实战中也会遇到问题。我把自己写二分踩过的坑集中整理一下对应的都是初学者最容易遇到的问题。第一个坑是循环条件写错。左闭右闭写成了left right导致区间还剩一个元素时循环提前退出。比如nums [1], target 1理想情况应该返回0但因为left0, right0不满足left right循环直接结束返回的是-1。排查方法很简单写完后用单元素数组跑一遍。第二个坑是更新边界写错。用左闭右闭时把right赋值成mid导致区间无法收缩。比如目标在左半区right被更新成mid而mid已经被检查过这样等于把已经排除的元素又放回搜索区间最后会在某个局部区间来回震荡形成死循环。这个问题在调试时最明显的特点是left和right的值反复横跳程序无法结束。第三个坑是目标值不存在时的行为。二分查找的常规做法是循环结束后返回-1但有些变种要求返回插入位置。704这道题的题意很清晰找不到就返回-1所以循环结束后统一return -1即可。但你要养成一个习惯写完后手动验证一轮目标值小于所有元素、大于所有元素、等于中间元素、等于首尾元素这四种场景。调试二分有一个特别高效的方法打印中间状态。你可以临时在循环里打印left、mid、right三个值看看每一轮的变化是否符合预期。这个方法看着笨但对初学者特别有效它能让你从“眼睛看代码”变成“数据驱动态”。2.4 二分法的进阶价值704只是一道最简单的二分查找但它的思想可以延续到很多更复杂的题。常见扩展包括查找第一个等于目标值的位置、查找最后一个等于目标值的位置、查找第一个大于等于目标值的位置、查找峰值元素、在旋转有序数组中查找目标值、在答案值域上进行二分等等。这些题目的共同核心都是通过一个单调条件把搜索空间一分为二逐步收敛。所以第一天如果能把704的边界逻辑彻底吃透后面的进阶题至少能省一半力气。3. 27.移除元素双指针的第一次亲密接触3.1 题目陷阱和暴力解法为什么慢27.移除元素的描述是给定一个数组nums和一个值val原地移除所有数值等于val的元素返回移除后数组的新长度且不需要考虑数组中超出新长度后面的元素。这里有个关键概念要先拎清楚数组的“删除”和链表的删除完全不同。链表的删除可以通过改变指针指向来“摘除”节点但数组在内存中是连续存储的你不可能真正释放中间某个位置能做的只有“用后面的元素覆盖前面的元素”。所以这道题本质上是问你如何高效地完成覆盖而不是想尽办法去“删除”。暴力解法是很多人第一反应的做法遍历数组遇到等于val的元素就把后面的所有元素整体往前移动一位。这个移动操作的时间复杂度是O(n)如果有多个位置需要删除最坏情况下整体复杂度达到O(n²)。空间复杂度倒是很优秀O(1)因为没有额外数组。但时间上O(n²)在数组规模大时会非常吃力。而且这种暴力解法在真实场景中还有个问题频繁的数组元素移动会引发大量内存拷贝缓存命中率也不高。所以双指针法才是这道题的重点它的思路可以类比成“原地重写数组”我不在乎元素原来的位置我只想得到一个不含目标值的新序列那就让一个指针去“读”另一个指针去“写”。3.2 快慢双指针快指针探路、慢指针写位双指针法的核心是两个索引一个快指针fast负责遍历整个数组寻找不等于val的元素一个慢指针slow负责记录下一个可以写入的位置。初始时fast和slow都从0开始。fast每遇到一个不等于val的元素就把这个元素赋值给nums[slow]并且slow。fast遇到等于val的元素就跳过不做任何写入操作。fast走完整条数组后slow的值刚好就是新数组的长度同时也是新数组最后一个元素的下一个位置索引。用生活化的话说快指针像一个质检员从头到尾扫过每个零件把合格品分拣出来慢指针像一个仓库管理员只负责把合格品按顺序码放。质检员走得快仓管员跟在其后两者步调不同但配合默契。这段逻辑用代码写出来非常短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; }我建议你在理解这段代码时不要把它当成一个“技巧”而要理解它背后的操作语义数组中的每个位置被扫描到的时候如果它是有效元素它就会被搬到一个“新数组”的前面去。这个“新数组”其实还是在原数组里因为我们已经不需要注意旧位置上的冗余数据了。这里有一个非常容易被忽略的细节slow多出来的位置会残留原值吗会但题目明确说了“不需要考虑数组中超出新长度后面的元素”所以这些残留数据可以忽略。这也是双指针法能做到空间O(1)的根本原因——我们借用了一些不会被读取的旧空间来临时存放垃圾数据逻辑上没有影响。3.3 为什么可以改变元素顺序这道题还有一个变种如果题目允许改变元素的相对顺序可以用左右双指针、一头一尾地交换进一步减少移动次数。当右边出现有效元素、左边出现需要删除的元素时就把右边的元素移到左边来覆盖掉无效元素。这个做法的优势在于遍历的次数变少了因为你只用一个left指针从左向右扫right只负责提供替换值。但代价是它改变了元素在数组中的相对顺序所以如果题目要求保持原有顺序就只能老老实实用快慢指针的版本。在LeetCode的27题中并没有要求保持相对顺序所以两种方案都可以AC。但从代码随想录训练营的教学角度讲我更建议先掌握快慢指针版因为它的可迁移性更强无论是删除重复项、移动零还是后续很多数组类题目本质上都用同一套快慢指针模式。左右夹逼的交换写法更适合作为一种“性能优化”的补充认知而不是首选模板。3.4 和后续题目的衔接快慢指针法在后续刷题中会高频出现。最典型的例子是26.删除有序数组中的重复项那道题也是快慢指针但要判断的是重复而不是指定值。再比如283.移动零把零都移到最后其实也是快慢指针的变体fast扫描遇到非零元素就写入slow位置结束后把slow到末尾统一填零。当你刷完这些题再回头看27会忽然反应过来原来三四个题都是同一个模板。第一天掌握了这个“双指针覆盖数组”的思维后面会遇到大量换汤不换药的题你只需要根据题意修改判断条件即可核心骨架完全不动。4. 977.有序数组的平方双指针从两端往中间走4.1 这题的坑在于平方会改变顺序977.有序数组的平方原题给的是一个非递减排序的数组要求返回每个值平方后组成的新数组且新数组也要按非递减排序。比如[-4, -1, 0, 3, 10]平方后得到[16, 1, 0, 9, 100]再排序后是[0, 1, 9, 16, 100]。很多人第一反应是直接每个数平方然后调库sort一下完事。这个做法时间复杂度是O(n log n)因为排序。LeetCode能过吗能过因为数据规模设计得比较宽松。但训练营把这道题放在第一天的用意很明显你不应该满足于能过而是要想清楚有没有更聪明的办法。关键观察在于原数组本身是有序的但经过平方以后负数部分会翻转顺序。比如[-4, -1]平方后是[16, 1]原本-1在-4后面平方后16反而在1前面了。所以整个平方数组呈现出一个特征元素大小从两端往中间递减。换句话说最大的值一定出现在最左端或最右端而不是中间。为什么因为平方函数在负数区间是单调递减的在正数区间是单调递增的两个单调段拼在一起最大值就只能出现在两端的某一个端点。你可以想象成一条抛物线的最低点在零附近越远离中心平方值越大。所以这道题的最优解思路也随之而来既然最大值的候选只在两端我们就可以用两个指针从两端往中间跑每次比较两端的平方大小把更大的那个填入结果数组的末尾位置。4.2 三种解法对比暴力排序、双指针、前两种的区别解法时间复杂度空间复杂度稳定排序是否依赖原数组有序直接平方sortO(n log n)O(n)需要排序不依赖任何数组都能做双指针从两端向中间O(n)O(n)天然有序必须依赖原数组有序所以双指针解法的时间复杂度是O(n)明显更优。在数据量上万或者百万级别的场景中O(n)和O(n log n)的差距非常大。这也是刷算法题时强调“不满足于暴力解”的原因真实系统里性能就是钱就是用户体验。需要提一句的是双指针解法需要一个长度为n的新数组来存放结果。这点很容易理解你总要返回一个新数组因为原数组需要同时参与两端的比较顺手写回原数组会干扰后续比较。4.3 从两端向中间的双指针写法我用这段代码说明双指针的核心流程vectorint sortedSquares(vectorint nums) { int n nums.size(); vectorint res(n); int left 0, right n - 1; int pos n - 1; while (left right) { int leftSquare nums[left] * nums[left]; int rightSquare nums[right] * nums[right]; if (leftSquare rightSquare) { res[pos] leftSquare; left; } else { res[pos] rightSquare; right--; } pos--; } return res; }这里有几个细节值得展开。第一个细节是pos的初始值必须是n-1而不是0。因为我们每次判断出的是当前两个候选中的最大值应该放在结果的最后面。如果你从前往后填结果你填进去的是“当前最大值”还是“当前最小值”从两端到中间的过程中其实最小值会慢慢浮出来但你不好确定具体位置所以倒着填最清晰。这也是一种很常见的双指针结果填充方式。第二个细节是判断leftSquare rightSquare相等时随便取哪一边代码里else分支把右边放进去再right--。实际运行时等号处理根本不影响最终数组的有序性因为两边值一样。第三个细节是循环条件写left right。这与左闭右闭区间一致。最后一次迭代时left等于right说明只剩一个元素了这个元素必然是剩余最小的平方值填到pos位置后循环结束整个数组刚好填满。整个过程像是一个“归并”的过程两个有序序列的反向合并。原数组的左侧部分平方后是降序右侧部分平方后是升序我们不断从两个序列的尾端取最大拼成最终的有序结果。这也是归并排序思想在特殊数据结构上的简版应用。4.4 进一步的延伸价值977的“双指针从两端往中间”的模式在后续刷题中同样会反复出现。比如167.两数之和II-输入有序数组以及一些判断回文串的双指针题都是相似的“左右夹逼”思路。可以说27是快慢双指针的入门977是对向双指针的入门这两类双指针构成了数组题里的两大主流双指针打法。第一天把这两条路都趟一遍后面你会特别感谢这个开篇组合。5. 实操中的翻车点与排查笔记5.1 二分死循环的真实现场我自己刚开始写二分时遇到过一个特别典型的死循环分享出来大家避个坑。当时用了左闭右闭的区间思路但更新时不小心写了right mid而不是right mid - 1。nums [1, 2, 3, 4, 5], target 1。第一次循环left0right4mid2nums[2]3大于1于是right mid变成了4。第二次循环left0right4mid2还是3大于1right还是4。循环永远在同一个状态上打转程序就死循环了。这种问题的本质是区间没有真正收缩。当right始终等于mid而mid又不小于等于left时区间长度没有减少自然无法退出循环。排错的办法很简单把right mid改成right mid - 1或者换到左闭右开版本中的right mid因为开区间中mid仍未检查区间确实可以缩小到[left, mid)。问题的关键在于闭区间中mid已经检查过必须排除。我自己的排查习惯是在while循环里临时输出left、mid、right三个值观察它们在新一轮是否至少有一个发生变化。如果连续两轮三者都一样那就几乎可以断定是区间收缩逻辑写错了。5.2 边界测试清单第一天做这三道题我强烈建议你别只满足于提交AC而是手动构造一组边界测试跑一遍。我常用的测试用例包括以下几种供你参考。二分查找空数组、只含一个元素的数组、目标是首元素、目标是尾元素、目标不存在小于最小、大于最大、介于中间但不存在的值、数组长度为偶数、数组长度为奇数。移除元素空数组、数组中全是val、数组中不含val、val在开头、val在结尾、多个连续val、多个不相邻的val。有序数组的平方全负数数组、全正数数组、包含0、只含一个元素、负数个数多于正数、正数个数多于负数。其中最容易在考场或面试里暴露问题的是“空数组”和“全删除”这两种场景。很多人的代码在普通用例上跑得好好的一遇到此类边界就凉了。比如二分查找中如果二分查找输入是空数组那么left0, right-1循环条件left right直接不满足返回-1逻辑上是正确的但你要确保自己没想到right初始化为一个无符号整型导致大量警告或异常。再比如移除元素中如果整个数组全是val那么slow最后保持为0返回长度0但你在检查返回结果前要先确认自己没把数组越界访问当成正常输出。5.3 三题复杂度与代码模板速查表我总结了一张第一天的速查表把三个题的核心信息放到一起方便后续复习。你不用背下来但最好能看着这个表把思路完整复述一遍。题目核心解法时间复杂度空间复杂度边界初始化要点704.二分查找左闭右闭二分O(log n)O(1)right n-1循环left rightright mid - 1 / left mid 127.移除元素快慢指针覆盖O(n)O(1)slow初始0fast扫描等于val就跳过977.有序数组的平方两端向中间双指针O(n)O(n)left0, rightn-1, posn-1比较平方值从结果数组尾部填入时间上二分查找的O(log n)是算法复杂度分析里的经典对数级别它意味着每次循环都会缩减一半搜索范围。28的O(n)是线性级别你只遍历了数组一遍。977的O(n)也是线性但需要额外O(n)空间存储结果这通常是可接受的因为返回值本身就需要新建一个等长的数组。5.4 第一天训练节奏建议训练营第一天最容易犯的错误是“刷完就忘”看完题解写出代码提交通过立刻进入下一题。这样的节奏看起来很高效实际留不下多少东西。我的建议是每道题多花十分钟做三件事一是口头复述思路不看代码把边界条件说清楚二是验证自己的极端用例手推一遍小规模数据而不是只在脑子里大概想想三是看看别人的解法比如二分查找是否有更简洁的递归写法27题是否有交换版本强迫自己跳出惯性。不要小看复盘这一步。我自己在刚刷题时经常是今天AC了下周再来一遍依旧卡壳就是因为少了这一步。训练营一共好多天后面的题目会不断复用这些基础能力第一天多花十分钟后面可能省下几个小时。写在最后第一天刷题的真实体感三题做完我最大的感受是算法题确实不需要死背模板但前提是你把每一步的为什么都想透了。二分查找的难点不在“取中间值”这件事上而在你对区间的定义是否始终保持一致移除元素给人的启发不是“双指针很妙”而是它揭示了数组底层没有删除只有覆盖的事实有序数组的平方则告诉你使用双指针前先观察数据本身的特征特征选对方法特征没找准就只能用笨方法。按照我自己的实操经验第一天这三个题值得你隔一周再做一遍但这次可以限时15分钟一题看看能否不假思索地写出正确代码。如果你能做到二分查找的边界意识、双指针的基本套路就算是真正内化了。到那个时候再进入后面的题目你会发现很多新题不过是这三道题的排列组合再套一层壳罢了。