当前位置：首页 > news >正文

双指针专题(二)：两头堵的智慧——「有序数组的平方」

news 2026/3/27 6:23:53

哈喽各位，我是前端小L。

场景想象：

给你一个已经排好序的数组 [-4, -1, 0, 3, 10]。

我们要把每个数平方，然后组成一个新的有序数组。

直觉做法：先把每个数平方[16, 1, 0, 9, 100]，然后调用sort()排序。
问题：sort()的复杂度是 $O(N \log N)$。面试官通常会问：“能不能用 $O(N)$ 解决？”

思考：

数组其实已经“部分”有序了。

负数部分：越往左，绝对值越大，平方后越大。
正数部分：越往右，绝对值越大，平方后越大。
也就是说，最大的平方数，一定是在数组的最左边或者最右边！不可能在中间。

力扣 977. 有序数组的平方

https://leetcode.cn/problems/squares-of-a-sorted-array/

题目分析：

输入：按非递减顺序排序的数组nums（包含负数）。
输出：每个数字的平方组成的新数组，也要按非递减顺序排序。

例子：[-4, -1, 0, 3, 10]

左边-4平方是16。
右边10平方是100。
100 > 16，所以100肯定是新数组里的老大（最后一名）。

核心思维：左右夹逼 + 逆序填充

既然最大的数一定在两头，那我们就派出两个指针：

左指针 (left)：指向开头（处理负数）。
右指针 (right)：指向结尾（处理正数）。
结果指针 (k)：指向新数组的最后一个位置（因为我们要先找最大的，填到最后去）。

操作逻辑：

比较nums[left]的平方和nums[right]的平方。
谁大选谁。
- 如果左边大：把左边的平方填入结果数组的k位置，left向右移。
- 如果右边大：把右边的平方填入结果数组的k位置，right向左移。
k指针向前移动一格，准备填倒数第二大的数。
当left > right时，结束。

代码实现 (JavaScript)

JavaScript

/** * @param {number[]} nums * @return {number[]} */ var sortedSquares = function(nums) { let n = nums.length; // 创建一个等长的新数组，用来存放结果 let result = new Array(n); let left = 0; let right = n - 1; // k 指向结果数组的最后一个位置（倒着填） let k = n - 1; // 注意：这里是 left <= right // 因为最后当 left === right 时，剩下的那个元素也要处理（平方后填入） while (left <= right) { let leftSquare = nums[left] * nums[left]; let rightSquare = nums[right] * nums[right]; if (leftSquare > rightSquare) { // 左边的平方更大，填入末尾 result[k] = leftSquare; left++; // 左指针向内收缩 } else { // 右边的平方更大（或相等），填入末尾 result[k] = rightSquare; right--; // 右指针向内收缩 } // 填完一个，k 往前挪一位 k--; } return result; };

深度模拟

输入：[-4, -1, 0, 3, 10]

初始：L=0(-4),R=4(10),k=4。
- 比较：(-4)²=16vs10²=100。
- 选右边。res[4] = 100。R变成 3。k变成 3。
- 状态：[-4, -1, 0, 3],res=[?, ?, ?, ?, 100]
第二轮：L=0(-4),R=3(3)。
- 比较：16vs9。
- 选左边。res[3] = 16。L变成 1。k变成 2。
- 状态：[-1, 0, 3],res=[?, ?, ?, 16, 100]
第三轮：L=1(-1),R=3(3)。
- 比较：1vs9。
- 选右边。res[2] = 9。R变成 2。k变成 1。
...以此类推，直到填满。