有序数组的平方：双指针从两端向中间归并

老张2026/4/30大约 5 分钟

有序数组的平方：双指针从两端向中间归并

适读人群：Java 后端工程师、算法初阶学习者 | 阅读时长：约 14 分钟 | 难度：⭐⭐

开篇故事

这道题是我用来给刚学双指针的同学讲"从两端向中间"模式的入门题。跟上一篇讲的"盛水容器"（从两端向中间收缩）不同，这道题的双指针方向也是从两端往中间，但目的是"归并"而不是"收缩"。

一个非递减的整数数组，里面可能有负数，平方之后绝对值最大的在两端（最负的和最正的），绝对值最小的在中间。这就决定了：从两端取绝对值最大的平方，放到结果数组的末尾，逐步填满结果数组。

这个思路非常直观，难度不高，但它很好地展示了"结果数组从后往前填充"这个技巧——当你无法直接从前往后确定结果时，反向填充是一个很好的思路。

一、题目解析

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

示例：

nums = [-4,-1,0,3,10]，输出：[0,1,9,16,100]
nums = [-7,-3,2,3,11]，输出：[4,9,9,49,121]

关键观察： 数组有序，但含负数时平方后的序不变。平方后的最大值一定在原数组两端之一，因为绝对值最大的在两端。

二、解法一：直接平方后排序（O(n log n)）

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

复杂度分析

时间复杂度：O(n log n)。排序的代价。
空间复杂度：O(n)。结果数组。

三、解法二：找负正分界点，两侧归并（O(n)）

public class Solution2 {
    public int[] sortedSquares(int[] nums) {
        // 找最后一个负数的位置
        int neg = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0) neg = i;
            else break;
        }

        int[] result = new int[nums.length];
        int idx = 0;
        int pos = neg + 1;  // 第一个非负数的位置

        // 类似归并两个有序数组
        while (neg >= 0 && pos < nums.length) {
            int negSq = nums[neg] * nums[neg];
            int posSq = nums[pos] * nums[pos];
            if (negSq <= posSq) {
                result[idx++] = negSq;
                neg--;
            } else {
                result[idx++] = posSq;
                pos++;
            }
        }
        while (neg >= 0) {
            result[idx++] = nums[neg] * nums[neg];
            neg--;
        }
        while (pos < nums.length) {
            result[idx++] = nums[pos] * nums[pos];
            pos++;
        }
        return result;
    }
}

复杂度分析

时间复杂度：O(n)。线性扫描。
空间复杂度：O(n)。结果数组。

四、解法三最优：对撞双指针，从后往前填充

思路分析

更简洁的做法：lo 从左端，hi 从右端，比较两端的平方，较大的填入结果数组的末尾，然后对应指针内移。

这样直接从最大值开始填，避免了找分界点的麻烦。

Mermaid 图

完整代码

public class Solution3 {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int lo = 0, hi = n - 1;
        int idx = n - 1;  // 从结果数组末尾开始填

        while (lo <= hi) {
            int loSq = nums[lo] * nums[lo];
            int hiSq = nums[hi] * nums[hi];

            if (loSq >= hiSq) {
                result[idx--] = loSq;
                lo++;
            } else {
                result[idx--] = hiSq;
                hi--;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();
        System.out.println(Arrays.toString(
                sol.sortedSquares(new int[]{-4,-1,0,3,10}))); // [0,1,9,16,100]
        System.out.println(Arrays.toString(
                sol.sortedSquares(new int[]{-7,-3,2,3,11}))); // [4,9,9,49,121]
        System.out.println(Arrays.toString(
                sol.sortedSquares(new int[]{-3,-1}))); // [1,9]
        System.out.println(Arrays.toString(
                sol.sortedSquares(new int[]{0,1,2}))); // [0,1,4]
    }
}

复杂度分析

时间复杂度：O(n)。lo 和 hi 各移动最多 n 次。
空间复杂度：O(n)。结果数组（不计入则为 O(1)）。

五、举一反三

题号	题目	关联点
88	合并两个有序数组	从后往前填充，避免覆盖
21	合并两个有序链表	两路归并的链表版本
986	区间列表的交集	双指针处理两个有序序列

"从后往前填充"这个技巧的应用场景：

当目标数组从前往后填充时，已填位置和待填位置会重叠；从后往前填充时，已填位置不会影响待读取的位置，避免了覆盖问题。LeetCode 88（合并两个有序数组，原地合并到 nums1）正是用了这个技巧。