企业官网建设流程全解析

LeetCode 977 有序数组的平方（Squares of a Sorted Array）全解：从 O(n log n) 排序到 O(n) 双指针

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇技术指南围绕 LeetCode 977「有序数组的平方」展开，结合本仓库（Leetcode solutions）中 Python、Java、C++、JavaScript、TypeScript、Go、Rust、Kotlin、Swift 共 9 种语言的源码实现，系统讲解「先平方再排序」「双指针正向收集 + 反转」「双指针反向填充」三种解法。读完本文，你将掌握双指针（Two Pointers）在有序数组问题中的典型应用模式，理解平方运算对数组有序性的破坏机制，并能够从 O(n log n) 优化到 O(n) 时间复杂度的线性解法。

问题回顾与前置知识

题目要求：给定一个按非递减顺序排序的整数数组nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

例如nums = [-4, -1, 0, 3, 10]，输出应为[0, 1, 9, 16, 100]（该示例出自仓库中的 C++ 实现注释）。

在动手解题前，需要先掌握以下三个知识点：

• 双指针技术（Two Pointers Technique）：同时从有序数组的两端比较元素，利用数组已排序的性质避免重复扫描。本问题的三种解法中两种都依赖该技术。
• 排序算法：理解排序 vs 线性遍历之间的时间复杂度权衡。内置排序通常为 O(n log n)，而基于有序性构造的双指针可以做到 O(n)。
• 绝对值（Absolute Values）：负数平方后变为正数，会改变元素间的大小顺序。这是本题最容易忽略的核心观察。

解法一：先平方再排序（O(n log n)）

直觉（Intuition）

最直接的思路是：先把数组中每个元素原地平方，再调用内置排序函数排序。由于原始数组虽然有序，但平方操作会让负数变为正数从而打乱顺序，因此平方后必须重新排序。

例如[-4, -1, 0, 3]平方后变为[16, 1, 0, 9]，需要排序成[0, 1, 9, 16]。

算法步骤

1. 遍历数组，将每个元素原地平方（nums[i] *= nums[i]）。
2. 调用语言内置的排序函数对整个数组排序。
3. 返回排序后的平方数组。

多语言实现

以下实现来自仓库的 Python（注意：仓库 Python 主文件采用双指针优化版，此处展示文档中的排序版思路）与各语言文件，其中 C++ 排序版 在注释中明确标注了该方案的时间复杂度：

class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: for i in range(len(nums)): nums[i] *= nums[i] nums.sort() return nums

public class Solution { public int[] sortedSquares(int[] nums) { for (int i = 0; i < nums.length; i++) { nums[i] *= nums[i]; } Arrays.sort(nums); return nums; } }

class Solution { public: vector<int> sortedSquares(vector<int>& nums) { for (int i = 0; i < nums.size(); i++) { nums[i] *= nums[i]; } sort(nums.begin(), nums.end()); return nums; } };

class Solution { /** * @param {number[]} nums * @return {number[]} */ sortedSquares(nums) { for (let i = 0; i < nums.length; i++) { nums[i] *= nums[i]; } nums.sort((a, b) => a - b); // 必须传入比较函数，避免按字典序排序 return nums; } }

public class Solution { public int[] SortedSquares(int[] nums) { for (int i = 0; i < nums.Length; i++) { nums[i] = nums[i] * nums[i]; } Array.Sort(nums); return nums; } }

func sortedSquares(nums []int) []int { for i := range nums { nums[i] *= nums[i] } sort.Ints(nums) return nums }

class Solution { fun sortedSquares(nums: IntArray): IntArray { for (i in nums.indices) { nums[i] *= nums[i] } nums.sort() return nums } }

class Solution { func sortedSquares(_ nums: [Int]) -> [Int] { var nums = nums for i in 0..<nums.count { nums[i] *= nums[i] } nums.sort() return nums } }

impl Solution { pub fn sorted_squares(mut nums: Vec<i32>) -> Vec<i32> { for x in nums.iter_mut() { *x *= *x; } nums.sort(); nums } }

注意：Swift 中nums是let常量参数，必须先var nums = nums复制一份才能原地修改；Rust 则利用mut nums参数所有权直接原地修改，两种语言体现了各自的所有权/可变性语义差异。

复杂度分析

• 时间复杂度：O(n log n)——遍历平方耗时 O(n)，内置排序耗时 O(n log n)。
• 空间复杂度：O(1) 或 O(n)——取决于所用排序算法的具体实现（原地排序如堆排序/快速排序为 O(1)，归并排序等为 O(n)）。

从仓库 C++ 实现 的注释可以看到该方案标注为Time: O(NlogN) / Space: O(N)，这正是面试中希望被你超越的基线。

解法二：双指针从两端比较 + 反转（O(n)）

直觉（Intuition）

由于输入数组本身是排好序的，平方值最大的元素一定出现在两端——最左侧的负数（绝对值可能很大）或最右侧的正数。利用左右两个指针同时向中间移动，每次比较两端元素的绝对值（或平方值），总是取较大者，就可以按「从大到小」的顺序收集平方结果，最后再反转即可得到升序数组。

算法步骤

1. 初始化两个指针：l指向数组开头，r指向数组末尾。
2. 创建一个空的result列表。
3. 当l <= r时循环：
   • 比较nums[l]与nums[r]的平方大小；
   • 将较大的平方值追加到result，并将对应的指针向中间移动一步。
4. 反转result（因为收集顺序是从大到小）。
5. 返回反转后的result。

多语言实现

仓库中的 JavaScript 与 TypeScript 实现均采用此思路，TypeScript 版如下（leftSqr > rightSqr时左指针前进，否则右指针前进）：

class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: l, r, res = 0, len(nums) - 1, [] while l <= r: if (nums[l] * nums[l]) > (nums[r] * nums[r]): res.append(nums[l] * nums[l]) l += 1 else: res.append(nums[r] * nums[r]) r -= 1 return res[::-1]

public class Solution { public int[] sortedSquares(int[] nums) { int l = 0, r = nums.length - 1; ArrayList<Integer> res = new ArrayList<>(); while (l <= r) { if (nums[l] * nums[l] > nums[r] * nums[r]) { res.add(nums[l] * nums[l]); l++; } else { res.add(nums[r] * nums[r]); r--; } } Collections.reverse(res); return res.stream().mapToInt(i -> i).toArray(); } }

class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int l = 0, r = nums.size() - 1; vector<int> res; while (l <= r) { if (nums[l] * nums[l] > nums[r] * nums[r]) { res.push_back(nums[l] * nums[l]); l++; } else { res.push_back(nums[r] * nums[r]); r--; } } reverse(res.begin(), res.end()); return res; } };

class Solution { /** * @param {number[]} nums * @return {number[]} */ sortedSquares(nums) { let l = 0, r = nums.length - 1; const res = []; while (l <= r) { if (nums[l] * nums[l] > nums[r] * nums[r]) { res.push(nums[l] * nums[l]); l++; } else { res.push(nums[r] * nums[r]); r--; } } return res.reverse(); } }

public class Solution { public int[] SortedSquares(int[] nums) { int l = 0, r = nums.Length - 1; var res = new List<int>(); while (l <= r) { int leftSq = nums[l] * nums[l]; int rightSq = nums[r] * nums[r]; if (leftSq > rightSq) { res.Add(leftSq); l++; } else { res.Add(rightSq); r--; } } res.Reverse(); return res.ToArray(); } }

func sortedSquares(nums []int) []int { l, r := 0, len(nums)-1 res := []int{} for l <= r { if nums[l]*nums[l] > nums[r]*nums[r] { res = append(res, nums[l]*nums[l]) l++ } else { res = append(res, nums[r]*nums[r]) r-- } } for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 { res[i], res[j] = res[j], res[i] } return res }

class Solution { fun sortedSquares(nums: IntArray): IntArray { var l = 0 var r = nums.size - 1 val res = mutableListOf<Int>() while (l <= r) { if (nums[l] * nums[l] > nums[r] * nums[r]) { res.add(nums[l] * nums[l]) l++ } else { res.add(nums[r] * nums[r]) r-- } } res.reverse() return res.toIntArray() } }

class Solution { func sortedSquares(_ nums: [Int]) -> [Int] { var l = 0 var r = nums.count - 1 var res = [Int]() while l <= r { if nums[l] * nums[l] > nums[r] * nums[r] { res.append(nums[l] * nums[l]) l += 1 } else { res.append(nums[r] * nums[r]) r -= 1 } } return res.reversed() } }

impl Solution { pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> { let (mut l, mut r) = (0usize, nums.len() - 1); let mut res = Vec::new(); while l <= r { if nums[l] * nums[l] > nums[r] * nums[r] { res.push(nums[l] * nums[l]); l += 1; } else { res.push(nums[r] * nums[r]); if r == 0 { break; } r -= 1; } } res.reverse(); res } }

Rust 版本中r的类型为usize（无符号整数），r -= 1时若r == 0会下溢 panic，因此需要在else分支中先判断r == 0再 break，这是无符号索引在 Rust 中的经典边界处理。

复杂度分析

• 时间复杂度：O(n)——左右指针各移动一次，每个元素只被访问一次。
• 空间复杂度：O(n)——用于存放输出数组（不含输入数组本身的额外开销）。

解法三：双指针反向填充（O(n)，免反转）

直觉（Intuition）

这是对解法二的进一步优化：既然我们每次都能确定当前「最大的平方」应当放在结果数组的末尾，那就不必先收集再反转，而是直接维护一个从结果数组末尾向前移动的写入下标resIndex，把每个平方值直接放到它的最终位置上。仍然用两个指针比较两端的绝对值，但省去了最后的反转步骤。

算法步骤

1. 创建一个与输入数组等长的result数组。
2. 初始化l = 0、r = n - 1、resIndex = n - 1（指向结果数组最后一个位置）。
3. 当l <= r时循环：
   • 比较nums[l]与nums[r]的绝对值大小；
   • 将较大的平方值放到res[resIndex]，并移动对应的指针；
   • 将resIndex减 1。
4. 直接返回result（无需反转）。

多语言实现

这是仓库中多数语言主文件的最终解法，例如 Python（其注释标注Time: O(n) / Space: O(1)，即输出数组不计入额外空间）、Java、Go 与 Rust：

class Solution: def sortedSquares(self, nums: List[int]) -> List[int]: n = len(nums) res = [0] * n l, r = 0, n - 1 res_index = n - 1 while l <= r: if abs(nums[l]) > abs(nums[r]): res[res_index] = nums[l] * nums[l] l += 1 else: res[res_index] = nums[r] * nums[r] r -= 1 res_index -= 1 return res

public class Solution { public int[] sortedSquares(int[] nums) { int n = nums.length; int[] res = new int[n]; int l = 0, r = n - 1, resIndex = n - 1; while (l <= r) { if (Math.abs(nums[l]) > Math.abs(nums[r])) { res[resIndex] = nums[l] * nums[l]; l++; } else { res[resIndex] = nums[r] * nums[r]; r--; } resIndex--; } return res; } }

class Solution { public: vector<int> sortedSquares(vector<int>& nums) { int n = nums.size(); vector<int> res(n); int l = 0, r = n - 1, resIndex = n - 1; while (l <= r) { if (abs(nums[l]) > abs(nums[r])) { res[resIndex] = nums[l] * nums[l]; l++; } else { res[resIndex] = nums[r] * nums[r]; r--; } resIndex--; } return res; } };

class Solution { /** * @param {number[]} nums * @return {number[]} */ sortedSquares(nums) { const n = nums.length; const res = new Array(n); let l = 0, r = n - 1, resIndex = n - 1; while (l <= r) { if (Math.abs(nums[l]) > Math.abs(nums[r])) { res[resIndex] = nums[l] * nums[l]; l++; } else { res[resIndex] = nums[r] * nums[r]; r--; } resIndex--; } return res; } }

public class Solution { public int[] SortedSquares(int[] nums) { int n = nums.Length; int[] res = new int[n]; int l = 0, r = n - 1, resIndex = n - 1; while (l <= r) { if (Math.Abs(nums[l]) > Math.Abs(nums[r])) { res[resIndex] = nums[l] * nums[l]; l++; } else { res[resIndex] = nums[r] * nums[r]; r--; } resIndex--; } return res; } }

func sortedSquares(nums []int) []int { n := len(nums) res := make([]int, n) l, r := 0, n-1 resIndex := n - 1 for l <= r { if abs(nums[l]) > abs(nums[r]) { res[resIndex] = nums[l] * nums[l] l++ } else { res[resIndex] = nums[r] * nums[r] r-- } resIndex-- } return res } func abs(x int) int { if x < 0 { return -x } return x }

class Solution { fun sortedSquares(nums: IntArray): IntArray { val n = nums.size val res = IntArray(n) var l = 0 var r = n - 1 var resIndex = n - 1 while (l <= r) { if (kotlin.math.abs(nums[l]) > kotlin.math.abs(nums[r])) { res[resIndex] = nums[l] * nums[l] l++ } else { res[resIndex] = nums[r] * nums[r] r-- } resIndex-- } return res } }

class Solution { func sortedSquares(_ nums: [Int]) -> [Int] { let n = nums.count var res = Int var l = 0 var r = n - 1 var resIndex = n - 1 while l <= r { if abs(nums[l]) > abs(nums[r]) { res[resIndex] = nums[l] * nums[l] l += 1 } else { res[resIndex] = nums[r] * nums[r] r -= 1 } resIndex -= 1 } return res } }

impl Solution { pub fn sorted_squares(nums: Vec<i32>) -> Vec<i32> { let n = nums.len(); let mut res = vec![0; n]; let (mut l, mut r) = (0usize, n - 1); let mut idx = n; while l <= r { idx -= 1; if nums[l].abs() > nums[r].abs() { res[idx] = nums[l] * nums[l]; l += 1; } else { res[idx] = nums[r] * nums[r]; if r == 0 { break; } r -= 1; } } res } }

仓库中 Python 实现 使用了一个更精巧的写法：res[r - l]直接利用左右指针的距离计算写入位置（r - l恰好从n - 1递减到0），省去了单独的resIndex变量；其注释明确标注Time: O(n) / Space: O(1)（输出数组不计入空间）。Go 与 Rust 实现则各自定义了abs辅助函数处理负数的绝对值。

复杂度分析

• 时间复杂度：O(n)——一次线性遍历完成全部计算与放置。
• 空间复杂度：O(n)——用于存放输出数组。

三种解法对比一览

当输入规模较大时，解法二与解法三相比解法一有明显的常数级到数量级的提升；解法三又在解法二的基础上省去了反转操作，代码意图也更清晰，是面试与工程实践中推荐的首选方案。

常见陷阱（Common Pitfalls）

陷阱一：误以为平方保持有序性

最常见的错误是认为「有序数组平方后仍然有序」。只要数组中存在负数，这个假设就不成立——负数平方后变为正数，其大小可能超过右侧原本更大的正数的平方。例如[-4, -1, 0, 3]平方后得到[16, 1, 0, 9]，显然不再有序，必须重新排序。

陷阱二：双指针直接比较原值而非绝对值/平方

使用双指针时，如果直接比较nums[l]与nums[r]的原始值而不是它们的绝对值或平方值，会得到错误结果。因为左端的负数（如-4）其平方16可能大于右端正数（如3）的平方9，但原值比较-4 < 3会得出相反结论。务必比较绝对值（abs）或平方值，这正是解法三中所有语言实现都显式调用abs/Math.abs/kotlin.math.abs的原因。

陷阱三：语言相关的边界与语法细节

• Rust 无符号下溢：usize类型的指针执行r -= 1前需检查r == 0，否则在r = 0时会 panic（见 rust/0977-squares-of-a-sorted-array.rs）。
• JavaScript 排序比较器：Array.prototype.sort默认按字符串字典序排序，直接nums.sort()会导致[100, 16, 9]这类错误顺序，必须传入(a, b) => a - b数值比较函数（见 javascript/0977-squares-of-a-sorted-array.js）。
• Swift 常量参数：nums是let常量，需要先var nums = nums建立可变副本才能原地修改（见 swift/0977-squares-of-a-sorted-array.swift）。

扩展思考：解题模式迁移

本题是「有序数组 + 双指针」模式的经典入门题，其核心观察——有序数组的极值总出现在两端，指针从两端向中间收敛即可在线性时间内构造结果——可以迁移到一系列相关问题：

• 合并两个有序数组（如 Merge Sorted Array）：同样从尾部向头部填充，避免覆盖未处理的元素；
• 有序数组去重 / 原地压缩：快慢指针在单端移动；
• 两数之和（有序版本）：左右指针根据和与目标的大小关系决定移动方向；
• 验证回文串 / 回文链表：两端指针向中间收敛比较。

掌握从「排序 → 双指针收集 → 反向填充」的逐步优化路径，比单纯记住本题答案更有价值：它展示了如何利用输入数据的有序性这一额外约束，把复杂度从 O(n log n) 压缩到 O(n)。

仓库相关资源

• 关联文档：articles/squares-of-a-sorted-array.md
• 各语言题解源码：Python python/0977-squares-of-a-sorted-array.py、C++ cpp/0977-squares-of-a-sorted-array.cpp、Java java/0977-squares-of-a-sorted-array.java、JavaScript javascript/0977-squares-of-a-sorted-array.js、TypeScript typescript/0977-squares-of-a-sorted-array.ts、Go go/0977-squares-of-a-sorted-array.go、Rust rust/0977-squares-of-a-sorted-array.rs、Kotlin kotlin/0977-squares-of-a-sorted-array.kt、Swift swift/0977-squares-of-a-sorted-array.swift
• 仓库根目录：README.md 可查看整体题解目录与组织方式

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode