977. 有序数组的平方

题目描述：

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

---

解题分析及思路：

方法：双指针

思路：

1. 找到数组中第一个非负数，作为数组的分界线，将数组分为两部分，左边是负数，右边是正数
2. 从分界线开始，使用双指针，分别指向负数和正数，比较两个指针所指向的数字的平方大小，将较小的数字放入结果数组中，同时移动指针，直到两个指针移动到数组的末端
3. 将剩余的数字放入结果数组中

func sortedSquares(nums []int) []int {
	var index int = 0
	for index < len(nums) && nums[index] < 0 {
		index++
	}
	var left int = index - 1
	var right int = index
	var result []int = make([]int, len(nums))
	index = 0
	for left >= 0 && right < len(nums) {
		if nums[left]*nums[left] > nums[right]*nums[right] {
			result[index] = nums[right] * nums[right]
			right++
		} else {
			result[index] = nums[left] * nums[left]
			left--
		}
		index++
	}
	for left >= 0 {
		result[index] = nums[left] * nums[left]
		left--
		index++
	}
	for right < len(nums) {
		result[index] = nums[right] * nums[right]
		right++
		index++
	}
	return result
}

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:19 ms,击败了74.61% 的Go用户
• 内存消耗:6.7 MB,击败了39.79% 的Go用户