企业官网建设流程全解析

很多人第一次刷 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 平方成 1，0 平方成 0，3 平方成 9，10 平方成 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 = 100，100 更大，所以结果数组最后一个位置放 100
• right 左移，指向 3，此时 left 还是 -4
• 再次比较 16 和 9，16 更大，放在倒数第二个位置
• left 右移，指向 -1；right 还在 3
• 比较 1 和 9，9 更大，放在倒数第三个位置
• right 左移，指向 0；left 在 -1
• 比较 1 和 0，1 更大，放在倒数第四个位置
• 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 res

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) { 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，你会发现很多代码骨架是能直接套的。

顺着这条线，整个双指针家族你都可以串起来：

它们都有一个共同的底层直觉：在有序数组中，双指针能帮你把"找一对""合并""去重"这类操作压到一次遍历。

5. 一点个人体会：遇到"有序"两个字，先别急着排序

我第一次做这道题时，写的就是暴力解。当时还觉得挺得意——因为 LeetCode 上很多题连暴力都写不顺，这题至少 AC 了。后来看题解才意识到，自己根本没理解题目为什么要强调"非递减"。从那以后，我给自己定了一个规矩：见到"有序数组"四个字，先暂停三秒，问自己一句——有序性能被利用吗？双指针、二分、前缀和、单调栈，哪个合适？

这三秒钟的习惯，后来帮我解决了不少看起来很难的题。比如 167 题两数之和，看到有序第一反应就是左右指针；再比如 658 找到 K 个最接近的元素，有序数组+双指针排除法也成立。刷题刷到后面，你会发现真正拉开差距的往往不是你会多少算法，而是你对"已知条件"的敏感度。

还有一个实操建议：写完代码一定要手动跑一个带负数的用例。我见过太多人用全正数用例测试，左手边的指针从来没赢过一次，代码逻辑其实有 bug 也发现不了。至少跑三组用例：全负数、有正有负、全正数，确保左右两个分支都被真实走到。

977 是个好题，短、小、精巧，适合作为双指针的第一课。把它彻底弄懂，比囫囵吞枣刷十个题有用得多。以后面试再遇到，我会先说暴力解，然后主动补一句："但给定有序数组，双指针可以做到 O(n) 时间、O(1) 额外空间。"然后边写边说思路，写完再随手验证一个含负数的例子。整个流程下来，面试官通常不会再往下追问——因为这道题能考的点，你已经全部覆盖到了。