有序数组的平方
题目描述
给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。-10^4 <= nums[i] <= 10^4
示例 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]
思路
题目要求
- 给定一个含负数的升序排列的数组，
- 返回每个数字的平方组成的新的升序数组
暴力解法：平方后排序
暴力解法没有利用题目中给到的条件：给定一个含正负数的升序数组。所以平方以后的大值肯定出现在两侧，不是左边就是右边（负数的平方为正数）。
双指针法：两个指针分别指向数组的首部和尾部，每次比较两个指针所指值的大小，将大的逆序放入新数组。将双指针从外向内移动不会发生数组越界问题。
注意
因为是逆序存入数组，所以for循坏的循坏变量i从len(nums)-1开始递减。
代码
Go
func sortedSquares(nums []int) []int { length := len(nums) left, right := 0, length-1 newNums := make([]int, length) for i := len(nums) - 1; i >= 0; i-- { if l, r := nums[left]*nums[left], nums[right]*nums[right]; l < r { newNums[i] = r right-- } else { newNums[i] = l left++ } } return newNums }
