很多人第一次刷 LeetCode 977 这道题的时候心里多半是这也能算 medium或者这不就是先把每个数平方一下再排个序吗。我在面试里见过这道题不下五次每次都能看到有人很流畅地写出平方加排序的解法然后在一句能不能做到 O(n) 时间、O(1) 额外空间的追问下卡住。今天就把这道题彻底讲透——它真正想考察的是你能不能利用输入数组已经有序这个条件用双指针把时间压到线性而这套思路几乎是双指针系列最温和的入门款吃透它后面刷合并有序数组、三数之和会顺很多。1. 先亮出最直白的暴力解能过但面试官为什么还要追问1.1 题目到底在问什么题目原文很短给你一个按非递减顺序排序的整数数组 nums返回每个数字的平方组成的新数组要求也按非递减顺序排序。比如 nums [-4,-1,0,3,10]输出就是 [0,1,9,16,100]。大部分人看到题的第一反应是这有什么难的先把 -4 平方成 16-1 平方成 10 平方成 03 平方成 910 平方成 100然后排个序[0,1,9,16,100] 就出来了。在 LeetCode 上这个暴力解是真的能 AC 的因为 n 最大也就 10^4 左右。写出来大概长这样def sortedSquares(nums): return sorted(x * x for x in nums)Java 版本也就是多几行public int[] sortedSquares(int[] nums) { int n nums.length; int[] res new int[n]; for (int i 0; i n; i) { res[i] nums[i] * nums[i]; } Arrays.sort(res); return res; }简单、直白、不容易出 bug。但如果你把它当成终极答案那这道题就白刷了。1.2 O(n log n) 到底浪费了什么暴力解的时间复杂度是 O(n log n)空间复杂度取决于语言——Python 的 sorted 会生成新列表Java 的 Arrays.sort 对 int 数组用的是双轴快速排序会有 O(log n) 的栈空间如果严格按结果数组来算还需要 O(n)。问题不在于多了一两个数量级而在于题目花了半句话告诉你数组是递增有序的你却完全没用上。对一个无序数组排序O(n log n) 是下限可一旦数组有序你手里就多了一张明牌。这道题给有序这个条件就是在暗示有比排序更好的解法而且好得多。我经常用个很土的例子来理解这件事你要整理一排本来已经按身高排好的人只需要他们报数后原地微调结果你非要把所有人打乱再按身高重新排一遍。能完成但完全没必要。1.3 面试官真正想听到的第一层回答面试中如果我先给出暴力解接下来一定会主动补一句但既然输入有序应该可以用双指针做到 O(n)。这句话本身就值不少分——它说明你看到了题目条件并且知道条件对应的常用手段。从暴力解到双指针差别不在于代码量而在于你是否建立了这样的条件反射看到有序数组第一反应不该是排序而应该是能不能用双指针/二分/归并来利用这个有序性。977 就是用来训练这个反射的最佳题目。2. 双指针的灵感来源平方后的最大值只可能在数组两端2.1 负数的平方会折返平方运算有一个很关键的性质负数的平方是正的而且负数越小绝对值越大平方反而越大。换句话说[-4,-1,0,3,10] 这些数平方后分别是 16、1、0、9、100。如果只看平方后的值它们的分布在数轴上是一个V字形——从左往右先变小到达某个最小值通常是 0 附近后再变大。这带来一个直接结论平方后的最大值只会出现在原数组的两端要么是最大的正数平方要么是最小的负数平方。这其实有点像中学物理里的山谷山峰图像。你可以把这个数组想成一条里面挤着气球的长管子有人从左端往里吹气负数平方大有人从右端往里吹气正数平方大两个气口都不好惹。要判断到底哪边吹的气最强只需要左右各量一次。2.2 一次只决定一个位置剩下的交给指针假设数组是 [-4,-1,0,3,10]左边 left 0指向 -4右边 right 4指向 10(-4)^2 16(10)^2 100100 更大所以结果数组最后一个位置放 100right 左移指向 3此时 left 还是 -4再次比较 16 和 916 更大放在倒数第二个位置left 右移指向 -1right 还在 3比较 1 和 99 更大放在倒数第三个位置right 左移指向 0left 在 -1比较 1 和 01 更大放在倒数第四个位置left 右移两个指针相遇都指向 0把 0 放到第一个位置循环结束最终得到的数组是 [0,1,9,16,100]。你发现了没有每次循环我们做的都是同一件事比较左右两端数字的平方把更大的那个放到结果数组的空位里。因为每次都拿走剩余元素中平方最大的那个那么留在后面的元素平方一定更小依次放下去结果自然是非递减的。2.3 为什么这个贪心过程不会漏掉中间元素有人可能会担心左侧的负数平方虽然一开始比不过右侧但会不会在某个瞬间冒出来其实不会——因为左手边的元素如果平方特别大它早就在某轮比较中胜出并拿走了没被拿走的平方一定都比已经拿走的元素小。每次操作都缩小待处理区间最终每个元素恰好被处理一次一个不漏。更严谨一点说我们是在维护两个有序序列负数部分平方后从右往左是递增的越靠近 0 的那一侧负数平方越小非负数部分平方后从左往右是递增的。双指针其实就是把这两个各自有序的小序列做一次归并只不过归并结果是直接从大到小输出的。理解到这一层后面遇到合并两个有序数组的变体题你会发现套路如出一辙。3. 完整实现与逐行拆解从后往前填一段代码通吃边界3.1 推荐写法从结果数组末尾往前填直接上最有代表性的 Python 版本def sortedSquares(nums): n len(nums) res [0] * n left, right 0, n - 1 pos n - 1 while left right: left_square nums[left] * nums[left] right_square nums[right] * nums[right] if left_square right_square: res[pos] left_square left 1 else: res[pos] right_square right - 1 pos - 1 return resJava 版本只是语法差异核心逻辑一模一样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) { int lsq nums[left] * nums[left]; int rsq nums[right] * nums[right]; if (lsq rsq) { res[pos--] lsq; left; } else { res[pos--] rsq; right--; } } return res; }三个指针的分工要记牢left指向当前尚未处理的区间最左端right指向尚未处理的区间最右端pos指向结果数组中下一个要填入的位置从最后一位开始往前移。每次比较完胜出的那一端指针向中间收缩pos固定减一。循环里的left right是带等号的这是很多人容易漏掉的地方——如果漏了等号最后 left 和 right 指向同一个元素时循环就停了导致正中间那个数没有被放入结果数组。带来的 bug 非常隐蔽大多数测试样例恰好从中间位置没填输出的数组看起来只差一个元素。3.2 另一种写法从小到大填最后反转也有人喜欢正着填每次把较小的那个平方放到结果数组的前面。思路是维护两个指针比较出较小值放前面。但这样做有个麻烦——你比较出较小值后另一个指针可能在一段时间内一直没被选中结果前面空位一直产生。最终实现往往要先把所有平方算到一个临时数组或者反过来用从后往前填再反转。如果非要正着填可以这样def sortedSquares(nums): n len(nums) res [0] * n neg [x * x for x in nums if x 0][::-1] pos_vals [x * x for x in nums if x 0] i j 0 for k in range(n): if j len(pos_vals) or (i len(neg) and neg[i] pos_vals[j]): res[k] neg[i] i 1 else: res[k] pos_vals[j] j 1 return res本质上就是在做两个有序序列的归并。代码更长还要额外构造列表反而不如从后往前填干净。两种方式的对比可以看下面这张表写法核心操作是否需要反转/归并代码可读性推荐度从后往前填推荐每次取较大的平方放到结果末尾否高逻辑线性高从前往后填每次取较小的平方放到结果开头通常是或用额外归并中容易绕中我的建议很直接新手上手就用从后往前填这一种写法。它避免了归并两个小数组的额外步骤也不存在结果顺序反了的问题唯一的心理门槛就是想明白为什么每次要拿大的——只要记住平方值最大的数一定在两端后面就全通了。3.3 边界与常见坑我逐个踩过漏等号while (left right)会让中心元素被跳过。用是安全的。直接用原值比较大小比较的是nums[left]和nums[right]而不是它们的平方。负数一多就翻车比如 [-5, -1]原值 -5 小但平方 25 大。一定要先算平方再比。pos用成了n结果数组下标越界或者填出空位。记住pos初值是n - 1。变量名没有语义面试官最烦i、j、k满天飞。left/right/pos或者lo/hi都行关键是让看代码的人立刻明白你的意图。如果代码提交后发现结果和预期不一致我推荐一个快速定位技巧在纸上手动模拟一个带负数的数组比如 [-5, -2, -1, 0, 4]把每一轮left、right、pos的值写出来两轮就能看出是哪一步逻辑错了。这比在 IDE 里打日志快得多。4. 面试追问与变体条件一变解法还成立吗4.1 追问一能不能做到 O(1) 额外空间题目的标准要求是使用 O(1) 额外空间也就是说除了返回的结果数组不能再用额外的线性辅助结构。双指针方案本身只用常数空间完全满足。但如果面试官把条件改成不分配新数组原地修改 nums 并保持有序你就要停下来想一想了。原地 O(n) 的解法并不是不存在但它需要额外的输出空间来暂存否则你无法同时做到从两端取数和原地覆盖。实际工程中如果非要原地最现实的方案是先整体平方再用 O(n log n) 排序——这和暴力解没有本质区别。所以面试时遇到这种追问正确做法是明确告诉面试官在必须原地且 O(1) 空间的前提下线性时间方案难以成立通常需要 O(n) 辅助空间或放弃线性时间。会沟通比会做题重要得多。那种闷头写了个看起来能过的原地方案、结果跑了半天发现覆盖冲突的场面我见过太多次。4.2 追问二原数组不是有序的怎么办如果输入根本无序比如 [3, -1, 4, -2]那有序这个条件就没了双指针的推导失效。这时候只能先平方再排序O(n log n) 就是最优解。这也反向说明977 的难度并不在平方而在有序。4.3 追问三有重复元素怎么办重复元素对解法没有影响。if left_square right_square这个判断里如果两边相等走 else 分支只收右边把重复值留在原地最终结果依然正确。你也可以用换成收左端都一样。因为平方相等时谁先被选走都不影响最终序列内容。4.4 变体合并两个有序数组的平方如果题目改成给你两个有序数组 nums1 和 nums2返回它们所有元素平方后的有序数组解法和我们上面讲的从前往后填归并一模一样本质就是双路归并。LeetCode 88 题合并两个有序数组也是同一套思想只是把平方去掉了。刷完 977 再去刷 88你会发现很多代码骨架是能直接套的。顺着这条线整个双指针家族你都可以串起来题目双指针用法977. 有序数组的平方从两端向中间收缩生成有序平方数组88. 合并两个有序数组从后往前归并避免覆盖26. 删除有序数组中的重复项快慢指针原地去重167. 两数之和 II左右指针向中间移动283. 移动零快慢指针把非零元素前移它们都有一个共同的底层直觉在有序数组中双指针能帮你把找一对合并去重这类操作压到一次遍历。5. 一点个人体会遇到有序两个字先别急着排序我第一次做这道题时写的就是暴力解。当时还觉得挺得意——因为 LeetCode 上很多题连暴力都写不顺这题至少 AC 了。后来看题解才意识到自己根本没理解题目为什么要强调非递减。从那以后我给自己定了一个规矩见到有序数组四个字先暂停三秒问自己一句——有序性能被利用吗双指针、二分、前缀和、单调栈哪个合适这三秒钟的习惯后来帮我解决了不少看起来很难的题。比如 167 题两数之和看到有序第一反应就是左右指针再比如 658 找到 K 个最接近的元素有序数组双指针排除法也成立。刷题刷到后面你会发现真正拉开差距的往往不是你会多少算法而是你对已知条件的敏感度。还有一个实操建议写完代码一定要手动跑一个带负数的用例。我见过太多人用全正数用例测试左手边的指针从来没赢过一次代码逻辑其实有 bug 也发现不了。至少跑三组用例全负数、有正有负、全正数确保左右两个分支都被真实走到。977 是个好题短、小、精巧适合作为双指针的第一课。把它彻底弄懂比囫囵吞枣刷十个题有用得多。以后面试再遇到我会先说暴力解然后主动补一句但给定有序数组双指针可以做到 O(n) 时间、O(1) 额外空间。然后边写边说思路写完再随手验证一个含负数的例子。整个流程下来面试官通常不会再往下追问——因为这道题能考的点你已经全部覆盖到了。