刷算法题这些年，我发现一个很有意思的现象：大家总爱挑战高难度题目，却容易在小题目上栽跟头。“977. 有序数组的平方”就是这么一道看起来平平无奇、实际暗藏思路的题。题目内容很简单：给你一个已经按非递减顺序排好的整数数组，把每个数字平方之后，依然按非递减顺序返回。很多人第一反应是先平方再排序，代码几分钟就能跑通，但完全没有触及这道题真正想考察的东西。它的价值在于，让你学会如何在有序数组上利用双指针把时间复杂度从 O(n log n) 降到 O(n)。无论你是刚入门算法，还是准备面试，我都建议把这道题当成双指针思维的经典入门案例来研究。下面我会从最直觉的解法讲起，一步步推导出最优解，再补充代码细节、边界测试和同类型题目的迁移方法，希望你能从中找到可以复用的套路。

1. 题目拆解：没那么简单的“送分题”

1.1 题目到底在问什么

首先我们需要对输入的定义有准确理解。所谓非递减顺序排列，通俗说就是后一个数永远大于等于前一个数，等价于我们常说的“升序”，只是把相等的情况也包含进来了。比如 [-4,-2,0,1,9] 就是一个合法输入，而 [3,1,2] 不是。题目要求我们把每个元素的平方算出来，再按同样的非递减规则排列输出。注意后面的“有序”是对平方后的新数组说的，不是指原数组每个元素自身有序，因为负数平方之后可能会变得非常大。为什么强调“非递减”而不是“严格递增”？因为输入里可能含有重复元素，比如 [-2,-2,0,2,2]，平方后会有多个相同的4。处理重复时，算法的每一步只需要比较绝对值大小，不需要额外处理相等的情况，这样代码才能保持简洁。

这道题在不少刷题平台上的通过率看起来很高，但它并不能被简单归类为“无脑平方排序”。如果你只是追求通过，那当然可以几分钟写完；但如果把它放在面试场景里，面试官更想听的是你能否发现原数组有序这个关键信息，并且利用它设计出更高效的解法。换句话说，题目表面是“平方”，内核却是“有序性”。对有序性的敏感程度，往往能区分一个人是真理解算法，还是只会背模板。这也是我今天想把这道题从头到尾讲透的原因。

1.2 最朴素的解法为什么只是“保底”

最容易想到的做法就是循环每个元素，原地修改成自己的平方，然后调用排序函数。举个例子，[-7,-3,2,3,11] 经过平方后变成 [49,9,4,9,121]，再排序就得到 [4,9,9,49,121]。这个解法在工程上完全没有问题，而且代码量极少，但它的时间复杂度是 O(n log n)，因为排序占了大头。如果输入规模是10万、100万，这个排序就会成为明显瓶颈。问题不在于排序本身慢，而在于我们没有使用“原数组已经有序”这个信息。类比一下，你手上有一摞已经按姓名拼音排好的员工档案，现在只需要把每个人按照某个新规则重排，你不会把所有档案重新打乱再排序，而是会想：既然旧顺序里有规律，能不能顺着规律走？

这道题给出的规律就是：平方后的最大值一定藏在原数组的两端。这个观察是后续所有优化思路的来源。暴力解法不是不能用，而是在面试场合更适合作为“我先说一个最直接方案”的铺垫。实际工作中，如果你明确知道数据规模很小，排序开销可以忽略，那直接用简单方案无可厚非。但面试官考察的是思维习惯，他希望看到你能从暴力解出发，继续追问“能不能更快”。所以我把暴力解法称为“保底方案”，它保证了你能给出一个正确答案，但不会让你从中获得太多成长。真正值得学习的，是接下来要讲的双指针思路。

2. 核心思路：双指针法是怎么想出来的

2.1 平方后的序列有什么隐藏规律

把数轴画出来，假设原数组是非递减的，那么它的大致分布有两种极端：全是负数、全是正数，或者中间存在正负分界点。无论哪种，平方之后最大的数都不会出现在数组中间，因为中间元素的绝对值较小。比如 [-9,-3,0,5,8]，平方后是 [81,9,0,25,64]，最大值81在原数组最左边，次大值64在最右边，再次大值25在右侧内部。这告诉我们：如果每次从当前数组的左右两端各取一个元素，比较两者平方后的大小，较大的那个一定就是剩余元素中平方最大的。这个规律对空数组、单元素数组也成立。单元素数组的左右两端是同一个元素，直接放进结果即可。

这个观察来源于一个很朴素的数学事实：一个数的平方大小只取决于它的绝对值，而一个有序数组的绝对值分布并不单调，但绝对值最大的元素一定出现在两端。因为数组按原值排序，正数部分越靠右绝对值越大，负数部分越靠左绝对值越大，所以最左端和最右端分别覆盖了负数绝对值最大和正数绝对值最大的情况。其余中间的元素，无论正负，绝对值都不可能同时大于这两个端点。于是就有了一个不断缩小范围的方案：每次确定一个结果位置，并删掉已经处理的一端，直到所有元素处理完。

2.2 从两端往中间“挤”的过程

具体做法是维护两个下标 left 和 right，开始时 left 指向第一个元素，right 指向最后一个元素。再准备一个和输入一样长的结果数组 res，同时维护一个填充下标 pos，初始指向结果数组的最后一个位置。每轮都比较 nums[left] 和 nums[right] 的平方大小，谁大就把谁放到 res[pos]，然后让对应的指针向中间移动一步，最后 pos 减一。为什么要从后往前填结果数组？因为我们每次找的是当前剩余元素中平方最大的那个，而最大结果应该放在最终数组的后面。如果从前往后填，反而需要先找到最小的元素，这不太容易直接确定。从后往前填，相当于先安排最大的“个头”，再安排次大的，整个填充过程就像两个人从队伍两端往里走，每次出一个当前最高的人站到后面。

当 left 和 right 相遇时，说明只剩一个元素，把它放进空位后循环结束。整个过程中每个元素只会被访问一次，所以时间复杂度是 O(n)。这个“两端夹逼”的模式就是双指针的经典形态。严格证明也不复杂：在每一轮开始前，未处理的区间是 [left, right]，其中所有元素的平方最大值一定来自 nums[left] 或 nums[right]，因为该区间在原数组中依然有序，绝对值最大者仍在两端。把较大者放到结果数组的当前末尾，问题就缩小为处理剩下的区间。这个归纳过程可以一直持续到区间为空，所以最终结果必然有序。

3. 代码实现：从伪代码到可提交的版本

3.1 Python实现与逐行解释

先给出完整可运行的版本：

class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: n = len(nums) res = [0] * n left, right = 0, n - 1 pos = n - 1 while left <= right: left_sq = nums[left] * nums[left] right_sq = nums[right] * nums[right] if left_sq >= right_sq: res[pos] = left_sq left += 1 else: res[pos] = right_sq right -= 1 pos -= 1 return res

核心逻辑只有几行。left_sq 和 right_sq 直接算平方，然后比较大小。选择“>=”而不是“>”是为了在相等时优先移动左指针，但这并不是必须的，两个方向都可以，结果不变。循环条件是 left <= right，保证了单元素数组也能进入循环处理。需要注意，我们在循环里做了两次平方运算，但总共加起来 n 个元素每个只算一次，所以没有重复开销。res 初始化为 n 个0，避免了 append 的动态扩容。如果你习惯用空数组然后 append，也完全可以，但顺序要反过来：每次把较大的结果 append 到新数组末尾，最后再 reverse 回来。两种写法本质一样，但初始化定长数组更直观，也更贴近“只用一次赋值填位”的思路。

3.2 其他语言变体与细节差异

Python 中整数没有溢出问题，但对于静态类型语言，平方计算就有讲究。以 Java 为例，如果 nums 里的元素范围很大，直接写 nums[left] * nums[left] 可能发生 int 溢出。稳妥的做法是在比较时转为 long，最后再转回 int。C++ 可以写成 abs((long long) nums[left]) 来避免 INT_MIN 取绝对值时的未定义行为。下面是一个 Java 版本：

public int[] sortedSquares(int[] nums) { int n = nums.length; int[] res = new int[n]; int left = 0, right = n - 1, pos = n - 1; while (left <= right) { long ls = (long) nums[left] * nums[left]; long rs = (long) nums[right] * nums[right]; if (ls >= rs) { res[pos--] = (int) ls; left++; } else { res[pos--] = (int) rs; right--; } } return res; }

注意这里用 long 先保存平方，再比较，最后转回 int，这样即使元素绝对值达到 10^9 级别，也不会在计算过程中溢出。题目给定的范围一般是 [-10^4, 10^4]，平方后 10^8，int 完全放得下。但很多面试官喜欢问：如果输入范围改成 [-10^9, 10^9] 怎么办？这时平方超过 int 上限，必须用 long long 或 long。平时写题就要养成这种意识，以后遇到大数题目不会慌。不同语言的另一个细节是数组长度是否可直接访问，Python 里用 len(nums)，C++ 里用 nums.size()，Java 里用 nums.length，剩下双指针逻辑完全一致。如果能手写实现一个语言版本，其他语言基本就是换皮，这也是我推荐大家用动态语言先理解思路的原因。

4. 边界条件、正确性证明与常见问题

4.1 边界样例验证

为了确保算法正确，拿几个典型输入跑一遍。第一个是全负数数组 [-5,-4,-3,-2]，平方后是 [25,16,9,4]，经过算法左右比较：最左平方25最大，放结果末尾，然后 -4 的16 和 -2 的4 比较，依此类推，最终结果 [4,9,16,25]。第二个是全正数 [2,3,4,5]，这种最简单，原数组平方后仍然有序，双指针从右往左挑大的，同样能得出正确答案。第三个是含 0 的正负混合数组 [-1,0,1]，三个平方分别是1、0、1，最终结果 [0,1,1]。算法会先比较左右两个1，把其中一个放入倒数第一个位置，然后剩下0和另一个1，再把1放入倒数第二个位置，最后0放最前。第四个是重复值数组 [-2,-2,0,2]，平方后 [4,4,0,4]，结果 [0,4,4,4]。因为没有要求相等值的先后顺序，所以重复元素怎么安排都对。

下表总结了这几类典型情况：

把这些样例跑完之后，你会确认算法覆盖了所有本质情况：全负、全正、有正有负、有零、有重复。如果数组只有一个元素，left 和 right 相等，循环仍然会执行一次，直接把这个元素的平方放进 res[0]，也不会出错。所以这个实现不需要额外处理数组长度为1的特殊分支。

4.2 刷题/面试时会踩的坑

第一个坑是循环条件写错。有些人写成 left < right，结果单元素数组不会进入循环，res 里会留下一个0。必须用 <= 或者单独处理长度为1的情况。第二个坑是填充方向搞反。如果从 res 的开头开始填充，每次拿到的是当前最大值，但当前最大值应该放在数组靠后位置，所以从前往后填会得到降序结果。解决方式要么像我们这样 pos 初始为 n-1，要么先 append 再 reverse。第三个坑是只考虑正负数，忽略重复值。其实重复值不影响双指针，但会影响你手推样例时对结果的预期。第四个坑是和面试官沟通时只说“用双指针”，却讲不清楚为什么左右比较能保证有序。建议用一句话解释：因为原数组有序，所以平方后最大的数只可能出现在两端，每次把两者中较大的放到结果末尾，相当于在缩小范围的同时构造降序输出，最后自然也就是有序的。

另外一个很容易被追问的点是：既然数组有序，能不能用二分法？这道题不适合直接二分，因为我们要输出的是所有元素的平方排序，不是查找某个值。如果一定要用二分，可以先找到负数和正数的分界点，然后把它看成两个有序数组的归并问题：左边是负数平方后的降序，右边是正数平方后的升序，再用归并方式合成。这种方法同样是 O(n)，但代码量比双指针要大。面试时如果被问到，可以坦白说“双指针更简洁，归并法也可以”，并简单描述一下过程，这会让面试官觉得你确实理解了多种解法之间的关系，而不是只会背代码。

5. 从一题到一类：双指针思路的迁移价值

5.1 同类型题目如何识别

双指针在很多题目里都是一把钥匙，尤其是“有序数组”“链表”“字符串”相关的问题。看到这几个特征，可以优先考虑双指针：第一，输入是排序数组；第二，需要比较元素大小或判断是否满足某个条件；第三，结果与元素位置顺序有关。例如“有序数组的两数之和”这道题，给定排序数组和目标值，用首尾指针根据当前和与目标值的大小移动其中一个指针，能够在线性时间内找到答案。再比如“回文判断”问题，左右指针逐个比对字符，遇到不匹配就返回 false。还有“三数之和”，先排序，然后固定一个数，剩下的区间用双指针找配对。

我把从 977 里提炼出的迁移要点记在笔记里：当需要使用两端信息共同决定一个结果时，双指针通常优于二分和暴力。因为双指针不会跳过任何元素，也不依赖于单调函数，只需要输入存在某种“有序性”。另外，双指针往往伴随着“从后往前填充”或者“首尾交换”这样的操作，如果你发现一个题解里两个下标在往中间移动，那大概率就是同一个套路。刷题经验积累到一定程度后，看到“有序数组”四个字，你的大脑就应该自动弹出一组候选方案：二分、双指针、滑动窗口。977 这道题的作用，就是帮你把“双指针”这个选项牢牢焊死在记忆里。

5.2 我的一些个人习惯

在刷题这件事上，我个人的习惯是拿到题目后先不急着写代码，而是在草稿纸上画一条数轴，把正数、负数、零的位置标出来。这道题画完数轴的一瞬间，双指针的方案基本就出来了。写代码时我也会注意几件小事：变量名尽量用左/右相关的名字，保证可读性；复杂度分析要跟着代码一起写，养成肌肉记忆；写完以后手动跑两个样例，尤其是全负和混合正负的情况。这些习惯让我在真正面试时能冷静地展示思路，而不是埋头写代码。977 这道题虽然简单，却是练习这些习惯的绝佳素材。每刷一遍，我对“有序”两个字的理解就会深一层，后面遇到更复杂的双指针题时，思路也更顺。