有序数组的平方为什么可以用双指针？如何避免平方后顺序被打乱？

简化版

有序数组平方后不一定仍然有序，因为负数平方会变大。

但最大平方值一定来自当前最左端或最右端，所以可以用双指针从两端比较，把较大的平方放到结果数组末尾。

指针向中间收缩，最终得到升序平方数组。

详细版

数组本身升序，例如 [-4,-1,0,3,10]。平方后如果直接映射会得到 [16,1,0,9,100]，顺序乱了。

由于原数组有序，绝对值最大的元素只可能在两端。用 left = 0、right = n - 1，再用 pos = n - 1 从结果数组末尾往前填。

每次比较 nums[left]^2 和 nums[right]^2，大的放到 ans[pos]，对应指针移动。

时间复杂度 O(n)，空间复杂度 O(n)。如果语言和题目允许覆盖原数组，也可以从后往前写回原数组。

完整版教学

一、为什么平方会破坏有序性

升序数组只保证数值从小到大，不保证绝对值从小到大。负数越小，平方后可能越大。例如 -4 < -1 < 0 < 3，但平方后 16 > 1 > 0 < 9。所以不能简单地逐个平方后认为仍然有序。

易错点：平方排序看的是绝对值大小，不是原始数值大小。

二、最大值为什么一定在两端

原数组升序时，中间元素的数值介于两端之间。平方后的大小由绝对值决定，而绝对值最大的候选只可能是最左侧的负数或最右侧的正数。中间元素的绝对值不会同时超过两端。

位置	可能特点	平方后可能性
左端	最小负数	绝对值可能最大
中间	接近 0	平方通常较小
右端	最大正数	绝对值可能最大

这就是用相向双指针的依据。

三、为什么从结果末尾开始填

每轮比较两端平方，拿到的是当前剩余元素中的最大平方值。如果结果数组要求升序，最大值应该放在最后。放完后，pos--，继续在剩余区间中找下一个最大值。

nums: [-4, -1, 0, 3, 10]
比较 16 和 100 -> ans[4] = 100
比较 16 和 9   -> ans[3] = 16
比较 1 和 9    -> ans[2] = 9

这个过程像从大到小倒着填答案。

四、代码模板

实现如下：

function sortedSquares(nums) {
  const n = nums.length
  const ans = new Array(n)
  let left = 0
  let right = n - 1
  let pos = n - 1
  while (left <= right) {
    const a = nums[left] * nums[left]
    const b = nums[right] * nums[right]
    if (a > b) {
      ans[pos--] = a
      left++
    } else {
      ans[pos--] = b
      right--
    }
  }
  return ans
}

循环条件是 left <= right，因为最后剩下一个元素时也需要填入结果。

五、和排序方案的对比

最简单的做法是先平方再排序，复杂度是 O(n log n)。双指针利用原数组已排序这一条件，把复杂度降为 O(n)。面试中如果没有利用“有序”条件，通常说明还没有抓住题眼。

nums.map(x => x * x).sort((a, b) => a - b)

这行代码能跑，但不是这题想考的最优思路。

六、常见误区与追问

• 误区：直接平方后返回。 负数平方会改变相对顺序，结果不一定有序。
• 误区：从结果开头填较小值。 最小平方值不一定在两端，可能在中间接近 0 的地方。
• 误区：循环写成 left < right。 最后一个元素会漏填。
• 追问：为什么不用二分找正负分界再归并？ 可以，但双指针从两端更短；分界归并也是 O(n)。
• 追问：空间能不能 O(1)？ 如果允许修改输入且不额外要求保留原数组，可以从后往前覆盖；常规题返回新数组即可。

这些追问本质都围绕“平方后的最大值在两端”。

七、加强记忆

这题记成“平方看绝对值，最大在两端，答案倒着填”。不要被原数组升序迷惑，负数平方后会翻身变大。每轮比较左右平方，把更大的放到结果末尾，指针向内收缩。这个模型和“盛水容器、两数之和”一样，都是排序或边界结构给了指针移动依据。