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]。算法步骤遍历数组将每个元素原地平方nums[i] * nums[i]。调用语言内置的排序函数对整个数组排序。返回排序后的平方数组。多语言实现以下实现来自仓库的 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 numspublic 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: vectorint sortedSquares(vectorint 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: Veci32) - Veci32 { 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由于输入数组本身是排好序的平方值最大的元素一定出现在两端——最左侧的负数绝对值可能很大或最右侧的正数。利用左右两个指针同时向中间移动每次比较两端元素的绝对值或平方值总是取较大者就可以按「从大到小」的顺序收集平方结果最后再反转即可得到升序数组。算法步骤初始化两个指针l指向数组开头r指向数组末尾。创建一个空的result列表。当l r时循环比较nums[l]与nums[r]的平方大小将较大的平方值追加到result并将对应的指针向中间移动一步。反转result因为收集顺序是从大到小。返回反转后的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; ArrayListInteger 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: vectorint sortedSquares(vectorint nums) { int l 0, r nums.size() - 1; vectorint 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 Listint(); 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 i1, 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 mutableListOfInt() 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: Veci32) - Veci32 { 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把每个平方值直接放到它的最终位置上。仍然用两个指针比较两端的绝对值但省去了最后的反转步骤。算法步骤创建一个与输入数组等长的result数组。初始化l 0、r n - 1、resIndex n - 1指向结果数组最后一个位置。当l r时循环比较nums[l]与nums[r]的绝对值大小将较大的平方值放到res[resIndex]并移动对应的指针将resIndex减 1。直接返回result无需反转。多语言实现这是仓库中多数语言主文件的最终解法例如 Python其注释标注Time: O(n) / Space: O(1)即输出数组不计入额外空间、Java、Go 与 Rustclass 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 respublic 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: vectorint sortedSquares(vectorint nums) { int n nums.size(); vectorint 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: Veci32) - Veci32 { 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)——用于存放输出数组。三种解法对比一览解法核心思路时间复杂度空间复杂度是否原地修改输入解法一排序平方后调用内置排序O(n log n)O(1) 或 O(n)取决于排序实现是解法二双指针 反转从两端取较大平方收集后反转O(n)O(n)输出数组否解法三双指针反向填充从两端取较大平方从末尾向前放置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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考