刚把day1的笔记整理完准备接着写day2的时候我发现了一件有点尴尬的事情我把题号记混了。本来是想写力扣27“移除元素”结果翻到题库才发现27跟“有序数组的平方”完全是两道题后者是力扣977。不过转念一想这两个题放在同一篇文章里反而更有意思——它们都是双指针的经典入门一个用相向指针解决有序数组平方后的排序一个用同向快慢指针做原地删除。一次打卡消化两道双指针正好把这类题的核心套路串起来。下面就是我这次刷题完整的过程记录包括写错的版本、改对的版本、以及一些代码之外的经验。1. 先澄清一个题号day2记录的是977不是271.1 我为什么会在标题里写下“27”我自己复盘了一下这事其实不算罕见。很多刷题日计划里会写类似“day2 数组专题移除元素 有序数组的平方”这样的列表两个题挨在一起。力扣27在你刷题列表里通常是“数组基础篇”的第一题而“有序数组的平方”常常紧随其后。等刷完27再点开下一题脑子里还残留着27这个编号顺手就把它写成了“力扣27 二.有序数组的平方和排序”。这也是为什么现在很多刷题打卡模板会把“题目编号”和“题目名称”分开记录编号只看题号页名称只看题目页避免你这种凭记忆合并信息的方式。所以先把结论放这儿本文主角是力扣977有序数组的平方顺带会把力扣27移除元素一起讲掉。这两个题在题目难度上都属于简单级别但它们是理解双指针思想最好的两个入门样本。1.2 力扣977题目原文与理解题目的要求非常短给你一个按非递减顺序排序的整数数组nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。例如输入nums [-4,-1,0,3,10] 输出[0,1,9,16,100]-4的平方是16-1的平方是10的平方是03的平方是910的平方是100。原数组是有序的但平方之后变成16、1、0、9、100这个顺序就乱了所以需要重新排序。这里有一个容易被忽略的细节题目说的是“非递减顺序”不是“严格递增顺序”。也就说数组里可能存在重复元素比如[-2, -1, 0, 0, 3]。这在实现算法时不影响核心逻辑但如果你以为“严格递增”可能在后面推导指针移动条件时产生误解以为两端的平方一定不相等。实际上nums[left]和nums[right]的平方完全可能相等比如[-2, 2]平方都是4。1.3 这题真正想考察的是什么力扣977的编号在题库里被放在“数组”分类下但核心考点其实是两个是否能看到“平方后最大值一定在原数组两端”这个规律。是否会用双指针把时间复杂度从 O(n log n) 降到 O(n)。第二个考点非常关键。如果你一上来就平方然后调Arrays.sortOJ也能通过因为n通常不大。但既然题目给了“有序数组”这个前提就说明它希望你能利用这个有序性而不是直接把它当成一个通用排序题来做。这其实是很多简单题背后的共同暗示——你能不能用题目给的条件省掉一个本可以省掉的步骤。2. 从暴力解到双指针有序数组平方的解题演进2.1 第一反应平方加排序的时间复杂度分析我最初写出来的版本应该是绝大多数人看到这题的第一反应public int[] sortedSquares(int[] nums) { int n nums.length; int[] ans new int[n]; for (int i 0; i n; i) { ans[i] nums[i] * nums[i]; } Arrays.sort(ans); return ans; }这个解法能跑通但要分析一下它到底做了什么平方的过程遍历一遍O(n)。排序的过程Arrays.sort对基本类型数组使用的是双轴快排平均时间复杂度O(n log n)。所以整体是O(n log n)额外空间是输出数组的大小O(n)。如果题目里的n是几万、几十万这个解法虽然不算很差但明显不是最优。有一个更容易被忽略的问题nums[i] * nums[i]存在整数溢出风险。题目一般会把n控制在10^4量级nums[i]的绝对值可能在10^4左右乘起来是10^8还在int范围内。但如果你在本地测试时自己造数据把元素放大到10^5以上平方结果就会超过int上限算出来是负数然后Arrays.sort会把负数排在最前面直接全错。这个我在本地测试时踩过后面会专门说。2.2 有序性这个隐藏条件的价值暴力解法的根本问题是它完全无视了“输入数组已经有序”这个信息。打个比方假设有一份名单本来就已经按姓氏拼音排好了。现在你要按照“姓名字数”重新排一次。最快的方法不是把所有人重新排序而是分开处理——拼音顺序在前的和在后的人个数可能本身就比较集中。回到数组本身。因为原数组是升序的所以负数平方后会变成一个从大到小的序列正数平方后保持从小到大。比如[-4,-1,0,3,10]负数部分平方后16, 1这已经是降序了。正数部分平方后9, 100这是升序。两个部分各自有序但合在一起是乱的。这时候你需要的不是一次全量排序而是一个“归并”操作。归并两个有序序列复杂度是O(n)在这个题里正好可以借双指针来实现。2.3 为什么直接排一遍浪费了题目给的条件写代码和做数学题一样题目给的条件不是摆设。如果输入里写了“有序数组”几乎所有针对有序结构的算法二分、双指针、归并都会优先考虑。对这道题来说你直接排序相当于把题目额外附赠的条件扔掉了。面试的时候面试官如果看到你Arrays.sort大概率会追问一句“能不能利用原数组有序做出O(n)的解法”如果你这时候才想到双指针虽然最终能写出来但印象分会差很多。刷题不是只为了“通过”而是要形成一种条件反射看到有序数组脑子里就要自动列出二分查找、双指针、归并这几个选项然后判断哪个最贴合题目要求。这道题贴合的显然是双指针。3. 双指针的思维模型平方后的最大值只会出现在两端3.1 数学直觉负数的平方改变了大小关系负数越大平方越大所以在原数组里排在最后面的正数平方是最大的同时排在数组最前面的负数它的绝对值可能也是最大的平方也可能很大。我们真正要比较的不是nums[left]和nums[right]本身的大小而是它们平方之后的大小。举个直观的例子nums [-5, -2, -1, 1, 2, 3]两端分别是 -5 和 3。(-5)^2 253^2 9。最大值是25来自左端。下一个最大值呢左端移到 -2右端还是3(-2)^2 43^2 9于是最大值变成9来自右端。每走一步我们都能确定当前剩余元素中平方最大的一项把它放到结果数组当前位置。这个思维模型的核心是一个升序数组平方的最小值可能出现在中间某个位置靠近0的数但平方的最大值一定出现在两端之一。所以“找最大”这件事天然适合从两头向中间收拢的指针。3.2 指针移动规则谁的平方更大谁先输出双指针的具体规则其实只有一句话比较左右指针指向的元素平方谁大就把谁放到结果数组“当前空位”的末尾然后移动对应的指针。这里有一个非常关键的点结果数组要从后往前填。因为每次我们都是“选最大”而结果要求是递增的所以最大的数应当放在结果的最后面。如果从前往后填就会填出一个从大到小的乱序结果还得再反转那就多此一举了。伪代码如下left 0 right n - 1 pos n - 1 while left right: if nums[left]^2 nums[right]^2: result[pos] nums[left]^2 left else: result[pos] nums[right]^2 right-- pos--为什么循环条件是left right而不是left right因为当两个指针相遇时还有一个元素没被处理。你可以自己试一下nums [1]如果条件是循环体一次都不会执行结果数组里什么都没填。这个等号是我一开始最容易漏掉的细节。3.3 循环不变量你每一步都守着一条不变量我可以把双指针的整个逻辑写成一条循环不变量每次进入循环前结果数组中pos 1到n - 1这一段已经是最终排序结果里最大的那几个元素并且它们已经按递增顺序摆好。因为每次循环都从左右两端挑一个当前最大值填进这一段的最前面这个区间会不断向左扩张。循环结束时pos -1说明整个结果数组都被填满而且每一步都守住了这个不变量。CLRS里讲算法证明时经常用循环不变量刷题时不一定需要写完整证明但有了这个思维你就能很清楚地回答“为什么这样填是合理的”这样的追问。面试的时候能说出这句不变量会显得你真的理解算法而不是背了个模板。4. 三种写法横向对比与边界条件4.1 标准写法新数组双指针从后往前填最常规也最好理解的实现是用一个和原数组等长的新数组双指针从两端向中间遍历从后向前填充结果。下面是Java版本public int[] sortedSquares(int[] nums) { int n nums.length; int[] result new int[n]; int left 0; int right n - 1; int index n - 1; while (left right) { int leftSquare nums[left] * nums[left]; int rightSquare nums[right] * nums[right]; if (leftSquare rightSquare) { result[index--] leftSquare; left; } else { result[index--] rightSquare; right--; } } return result; }对应Python版本def sorted_squares(nums): n len(nums) result [0] * n left, right 0, n - 1 for i in range(n - 1, -1, -1): if abs(nums[left]) abs(nums[right]): result[i] nums[left] * nums[left] left 1 else: result[i] nums[right] * nums[right] right - 1 return result注意Python里我用了abs(nums[left]) abs(nums[right])来比较这是一个小技巧平方的比较其实就是绝对值的比较。用abs可以让代码更简洁也能少写两处乘法。但Java里Math.abs对int的极端值会有边界问题比如Integer.MIN_VALUE所以Java版本我选择直接乘方避免引入不必要的风险。4.2 各种变体原地修改、从头填、for循环怎么选变体A原地修改。能不能不开新数组理论上不行因为你一边遍历原数组一边在原数组上覆盖写会破坏后续判断需要的原始数据。比如你把nums[0]覆盖掉之后比较两端时左端的数据就已经不是原来的了。所以这个题的标准做法都是开新数组。变体B从前往后填。有人会想既然最大值在两端那我先找出最小值填到结果数组最前面然后依次往后面填。找最小值确实也能用双指针需要比较左右两端哪个平方更小。这个思路在nums全为正数或全为负数时比较直观但一旦数组有正有负最小的平方不一定在左右端点可能在中间靠近0的负数或正数。两端的值比较不出来还得额外判断符号逻辑就乱了。所以“从前往后填”在这个题里非常别扭不如“从后往前填”自然。变体Cfor循环代替while。因为循环次数就是数组长度n所以可以写成for (int left 0, right n - 1, index n - 1; left right; index--) { // 循环体 }这种写法把三个指针的初值都塞进for语句里看着紧凑但可读性一般。我的建议是刷题时优先保证可读性面试时如果能顺畅解释逻辑while版本完全够用不必为了炫技做这种压缩。4.3 直接踩坑经验边界、溢出、空数组我实际写这个题的时候踩了三个坑这里重点说一下。坑一漏了等号。第一次写循环条件我写的是left right结果nums [1]这种只有一个元素的数组直接返回全0。测试用例一跑直接红灯。这个等号问题在双指针题里非常常见建议形成习惯只要循环里需要处理“中间最后那个元素”就用left right如果是“两两配对”的场景比如从两端往中间找两数之和才用left right。坑二本地造大数测试时溢出。我在本地想验证大数组性能直接把nums的元素范围设到[-10^5, 10^5]平方后是10^10已经超过Integer.MAX_VALUE。结果平方值变负数双指针把负数当成最小值结果数组一团糟。后来我改成用long计算平方或者控制测试数据不要超过10^4才把这个坑绕过去。坑三空数组。如果输入是[]我的代码因为while条件不成立返回new int[0]看起来没问题。但如果你在代码里用了result[0]去初始化或者用nums[0]作为某种初始参考值空数组就会直接越界。所以写的所有代码在提交前先对着边界用例检查一遍空数组、单元素数组、全是负数、全是正数、正负混合。4.4 三种题的复杂度对比解法时间复杂度空间复杂度核心思路暴力平方排序O(n log n)O(n)简单直接不考虑有序性双指针从后往前填O(n)O(n)相向指针利用有序性排序后原地覆盖O(n log n)O(1)先平方再快排空间更省这里有一个值得注意的点如果不要求保持原数组不变你可以直接在原数组上先平方再排序空间复杂度是O(1)。但是如果要求“返回新数组且原数组不改变”就必须申请额外空间。OJ通常不检查原数组是否被修改但从工程规范来说函数的副作用越少越好所以标准解法开一个结果数组是最稳妥的。5. 顺带把力扣27移除元素一起解决快慢指针的常见套路5.1 力扣27的题目本质既然开头提到了题号记混的事那这篇就把27一起复盘了。力扣27“移除元素”是这么说的给你一个数组nums和一个值val你需要原地移除所有数值等于val的元素并返回移除后数组的新长度。不要使用额外的数组空间元素的顺序可以改变。这题的难点在于“原地”你不能新建一个数组把不等于val的数复制进去只能在原数组上操作。它的本质是“元素的覆盖写”——把不等于val的元素一个个往前挪挪到前面去让等于val的元素被覆盖掉。5.2 同向快慢指针实现力扣27用的双指针和977不一样。977是相向指针一个在头一个在尾27这个题用的是同向指针也叫快慢指针。慢指针指向“下一个要赋值的位置”快指针遍历整个数组。public int removeElement(int[] nums, int val) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! val) { nums[slow] nums[fast]; slow; } } return slow; }逐步走一遍快指针每遇到一个不等于val的元素就把它复制到慢指针的位置然后两个指针都前进一步快指针遇到等于val的元素则跳过慢指针不动。这样所有不等于val的元素都被按顺序往前挪最终slow的值就是新数组的长度。数组末尾剩下的那些位置是什么值、是什么顺序都不重要了。这个解法的复杂度是O(n)时间、O(1)空间比暴力解法“先数有几个不等于 val 再一个个搬”要干净得多。5.3 相向与同向双指针的两种分类把977和27放在一起看你会发现双指针其实是两大类相向指针左指针从头部出发右指针从尾部出发向中间靠拢。最常见于有序数组的查找、求和、反转。典型题目力扣977、力扣167两数之和 II、力扣11盛最多水的容器。同向指针两个指针从同一端出发一个快一个慢。最常见于原地删除、去重、滑动窗口。典型题目力扣27、力扣26删除有序数组中的重复项、力扣283移动零。刷双指针题时第一步不是急着写代码而是先判断这道题适合相向还是同向。判断依据很简单如果题目输入是“有序数组”并且要找的东西和“极值”“两个端点”有关多半是相向指针如果题目要“原地覆盖”“保持相对顺序”“去掉某些元素”多半是同向快慢指针。这条判断逻辑如果能内化后面再遇到“有序数组”“原地删除”两个高频词你的第一反应就不会是“我该用哪套板子”而是“这题是相向还是同向”。6. 从平方排序延伸到排序基础什么时候该用什么排序6.1 为什么有序数组平方不需要调用排序函数很多人学排序算法时会陷入一个误区任何需要有序输出的问题先无脑sort。但排序算法的时间复杂度下限在“基于比较”的排序模型下是O(n log n)。像力扣977这种题目数组本身已经有序只是经过平方变换后被打乱了。这种“一部分逆序、一部分正序两头大中间小”的特殊结构反而给了我们比排序更快的O(n)解法。这就引出一个更高级的思维排序是一个通用方案但针对特定数据结构针对特定的变换方式可能有比通用排序更快的算法。比如如果数组元素范围很小比如都在[0, 100]之间可以用计数排序做到O(n k)。如果数组接近有序插入排序的实际表现可能非常接近O(n)。如果数组本身就是“两端大、中间小”那你需要的其实就是一次归并而不是排序。刷排序算法题时如果你每次都直接sort看起来是省事了但也失去了思考“这个输入结构适合什么算法”的机会。这道平方题本质上就是在教你“识别输入的特殊结构避开通用排序”。6.2 排序稳定性在平方题里有没有用聊到排序就绕不开“稳定性”这个概念。稳定排序算法比如归并排序、插入排序能保证相等元素的相对顺序不变不稳定排序比如快排、选择排序则可能打乱。不过在这个平方题里我们完全没有去依赖“相等元素的相对顺序”因为元素都是平方后的整数相同的平方值谁在前谁在后再小不过了。所以这题根本没有必要讨论稳定性。 但“稳定性”这个概念对你刷其他题就有用比如你有一组对象先按姓名排好了现在要按年龄排序希望年龄相同的人仍然保持姓名的顺序这时候就必须用稳定排序。Java的Arrays.sort对对象数组使用稳定归并排序对基本类型数组使用不稳定双轴快排这个差异在特定业务场景下会直接影响结果。6.3 几种常用排序在这个场景的取舍虽然双指针是这道题的最优解但如果我们把它当成一道“先平方再排序”的简化题那不同排序算法的取舍也值得思考排序方法时间复杂度平均空间复杂度是否稳定在这个场景的适用性双指针归并思想O(n)O(n)稳定最优利用原数组有序快速排序O(n log n)O(log n)不稳定通用但浪费有序性归并排序O(n log n)O(n)稳定也浪费有序性计数排序O(n k)O(k)稳定如果值域小也可以插入排序O(n^2) 最坏O(1)稳定只在近乎有序时有优势你可能注意到我在“双指针归并思想”那行写的是“稳定”它确实稳定因为每次我们比较的左右两端如果平方相等默认取右端的。这个细节不影响结果但如果你在此基础上扩展成排序对象的版本稳定性就是一个需要认真对待的问题。6.4 给后续刷题的一个小建议从这道题出发我顺带把数组排序相关的知识点梳理了一遍选择排序、希尔排序、快速排序、归并排序、计数排序每一个都是值得单独花时间刷的专题。我的建议是不要一次性全学而是按照“暴力解法 - 优化思路 - 底层原理 - 实际应用”的节奏推进。比如今天这道平方题先学双指针再回头看排序算法你会发现前面那些复杂度公式突然就活了。最后再分享一个小技巧刷双指针题最容易出的bug就是边界条件。我自己在这道题上无论是977还是27都犯过“漏等号”和“忘记空数组”的问题。后来我想了个笨办法每道双指针题都先列出边界用例清单空数组、单元素、全相等、一正一负、全是负数、全是正数写代码前先在注释里写清楚每个用例的预期输出再动手实现。这个习惯帮我躲开了很多看不见的坑也省下了反复提交试错的时间。如果你也刚开始刷力扣不妨试一试这种“注释先行”的笨办法。