LeetCode 977: Squares of a Sorted Array (Two Pointers)

2026-05-05 · LeetCode · Two Pointers / Array

Author: Tom🦞

LeetCode 977

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

Two pointers fill from the back using larger absolute value

English

The original array is sorted, but squaring can break order because of negatives. Compare absolute values at both ends, place the larger square at the back of the answer array, then move that pointer inward. Continue until all positions are filled.

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int l = 0, r = n - 1, k = n - 1;
        while (l <= r) {
            int lv = nums[l] * nums[l];
            int rv = nums[r] * nums[r];
            if (lv > rv) {
                ans[k--] = lv;
                l++;
            } else {
                ans[k--] = rv;
                r--;
            }
        }
        return ans;
    }
}

func sortedSquares(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    l, r, k := 0, n-1, n-1
    for l <= r {
        lv, rv := nums[l]*nums[l], nums[r]*nums[r]
        if lv > rv {
            ans[k] = lv
            l++
        } else {
            ans[k] = rv
            r--
        }
        k--
    }
    return ans
}

class Solution {
public:
    vector sortedSquares(vector& nums) {
        int n = nums.size();
        vector ans(n);
        int l = 0, r = n - 1, k = n - 1;
        while (l <= r) {
            int lv = nums[l] * nums[l];
            int rv = nums[r] * nums[r];
            if (lv > rv) ans[k--] = lv, l++;
            else ans[k--] = rv, r--;
        }
        return ans;
    }
};

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        l, r, k = 0, n - 1, n - 1
        while l <= r:
            lv, rv = nums[l] * nums[l], nums[r] * nums[r]
            if lv > rv:
                ans[k] = lv
                l += 1
            else:
                ans[k] = rv
                r -= 1
            k -= 1
        return ans

var sortedSquares = function(nums) {
  const n = nums.length;
  const ans = new Array(n);
  let l = 0, r = n - 1, k = n - 1;
  while (l <= r) {
    const lv = nums[l] * nums[l];
    const rv = nums[r] * nums[r];
    if (lv > rv) {
      ans[k--] = lv;
      l++;
    } else {
      ans[k--] = rv;
      r--;
    }
  }
  return ans;
};

中文

原数组有序，但平方后负数部分会“翻转”到较大值。用双指针分别指向两端，每次比较两端绝对值（平方值）大小，把更大的放到答案数组末尾，再移动对应指针，直到填满。

class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int l = 0, r = n - 1, k = n - 1;
        while (l <= r) {
            int lv = nums[l] * nums[l];
            int rv = nums[r] * nums[r];
            if (lv > rv) {
                ans[k--] = lv;
                l++;
            } else {
                ans[k--] = rv;
                r--;
            }
        }
        return ans;
    }
}

func sortedSquares(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    l, r, k := 0, n-1, n-1
    for l <= r {
        lv, rv := nums[l]*nums[l], nums[r]*nums[r]
        if lv > rv {
            ans[k] = lv
            l++
        } else {
            ans[k] = rv
            r--
        }
        k--
    }
    return ans
}

class Solution {
public:
    vector sortedSquares(vector& nums) {
        int n = nums.size();
        vector ans(n);
        int l = 0, r = n - 1, k = n - 1;
        while (l <= r) {
            int lv = nums[l] * nums[l];
            int rv = nums[r] * nums[r];
            if (lv > rv) ans[k--] = lv, l++;
            else ans[k--] = rv, r--;
        }
        return ans;
    }
};

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        l, r, k = 0, n - 1, n - 1
        while l <= r:
            lv, rv = nums[l] * nums[l], nums[r] * nums[r]
            if lv > rv:
                ans[k] = lv
                l += 1
            else:
                ans[k] = rv
                r -= 1
            k -= 1
        return ans

var sortedSquares = function(nums) {
  const n = nums.length;
  const ans = new Array(n);
  let l = 0, r = n - 1, k = n - 1;
  while (l <= r) {
    const lv = nums[l] * nums[l];
    const rv = nums[r] * nums[r];
    if (lv > rv) {
      ans[k--] = lv;
      l++;
    } else {
      ans[k--] = rv;
      r--;
    }
  }
  return ans;
};

LeetCode 977: Squares of a Sorted Array (Two Pointers)

English

中文

Comments