刚把day1的笔记整理完，准备接着写day2的时候，我发现了一件有点尴尬的事情：我把题号记混了。本来是想写力扣27“移除元素”，结果翻到题库才发现，27跟“有序数组的平方”完全是两道题，后者是力扣977。不过转念一想，这两个题放在同一篇文章里反而更有意思——它们都是双指针的经典入门，一个用相向指针解决有序数组平方后的排序，一个用同向快慢指针做原地删除。一次打卡消化两道双指针，正好把这类题的核心套路串起来。下面就是我这次刷题完整的过程记录，包括写错的版本、改对的版本、以及一些代码之外的经验。
1. 先澄清一个题号：day2记录的是977不是27
1.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的平方是1，0的平方是0，3的平方是9，10的平方是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.sort，OJ也能通过，因为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 = 25，3^2 = 9。最大值是25，来自左端。下一个最大值呢？左端移到 -2，右端还是3，(-2)^2 = 4，3^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的负数或正数）。两端的值比较不出来，还得额外判断符号，逻辑就乱了。所以“从前往后填”在这个题里非常别扭，不如“从后往前填”自然。
变体C：for循环代替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，都犯过“漏等号”和“忘记空数组”的问题。后来我想了个笨办法：每道双指针题都先列出边界用例清单，空数组、单元素、全相等、一正一负、全是负数、全是正数，写代码前先在注释里写清楚每个用例的预期输出，再动手实现。这个习惯帮我躲开了很多看不见的坑，也省下了反复提交试错的时间。如果你也刚开始刷力扣，不妨试一试这种“注释先行”的笨办法。
