LeetCode 977. 有序数组的平方

Categories:

题目描述
思路分析
1. 解法一：双指针（推荐）
相似题目

题目描述

✅ 977. 有序数组的平方

思路分析

解法一：双指针（推荐）

核心思路：

数组是非递减排列，负数的平方可能大于正数的平方，因此最大的平方值一定出现在数组的两端。

设左指针指向数组头部，右指针指向数组尾部，每次比较两端的平方值，将较大的那个从结果数组的末尾填入。

左指针向右移动，右指针向左移动，直到两指针相遇，结果数组即为答案。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组的长度，只需一次线性遍历。

空间复杂度：O(n)，其中 n 表示数组的长度，需要额外分配一个等长的结果数组。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        // 左右指针分别指向数组两端
        int left = 0;
        int right = n - 1;
        // 从结果数组末尾开始填入最大平方值
        int pos = n - 1;
        while (left <= right) {
            int leftSquare = nums[left] * nums[left];
            int rightSquare = nums[right] * nums[right];
            // 较大的平方值填入当前位置
            if (leftSquare > rightSquare) {
                result[pos] = leftSquare;
                left++;
            } else {
                result[pos] = rightSquare;
                right--;
            }
            pos--;
        }
        return result;
    }
}

func sortedSquares(nums []int) []int {
	n := len(nums)
	result := make([]int, n)
	// 左右指针分别指向数组两端
	left, right := 0, n-1
	// 从结果数组末尾开始填入最大平方值
	pos := n - 1
	for left <= right {
		leftSquare := nums[left] * nums[left]
		rightSquare := nums[right] * nums[right]
		// 较大的平方值填入当前位置
		if leftSquare > rightSquare {
			result[pos] = leftSquare
			left++
		} else {
			result[pos] = rightSquare
			right--
		}
		pos--
	}
	return result
}

相似题目

题目	难度	考察点
88. 合并两个有序数组	简单	双指针、从后往前归并
167. 两数之和 II - 输入有序数组	中等	双指针、对撞指针
11. 盛最多水的容器	中等	双指针、对撞收缩
15. 三数之和	中等	双指针、排序后对撞
16. 最接近的三数之和	中等	双指针、排序后对撞
189. 轮转数组	中等	数组操作、双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/00756785