# 题目

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

977. 有序数组的平方 - 力扣（LeetCode）

# 分析

暴力解法可以直接每个数平方然后直接排序

	// 时间复杂度 o（n+nlogn）
	class Solution {
	public:
	vector<int> sortedSquares(vector<int>& A) {
	for (int i = 0; i < A.size(); i++) {
	A[i] *= A[i];
	}
	sort(A.begin(), A.end()); // 快速排序
	return A;
	}
	};

双指针法

这里数组有序，但平方过后负数可能更大，所以数组的最大值在数组两端，可以考虑用双指针法，i 指向起始位置，j 指向终止位置。左右两边挨个平方比较，大的方新数组末尾，然后 ++。

	// 时间复杂度为 O (n)
	class Solution {
	public:
	vector<int> sortedSquares(vector<int>& A) {
	int k = A.size() - 1;
	vector<int> result(A.size(), 0);
	for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要 i <= j，因为最后要处理两个元素
	if (A[i] * A[i] < A[j] * A[j]) {
	result[k--] = A[j] * A[j];
	j--;
	}
	else {
	result[k--] = A[i] * A[i];
	i++;
	}
	}
	return result;
	}
	};

相向双指针法（也称为对撞双指针法）是双指针法的一种特殊形式。它使用两个指针从数组或字符串的两端开始，向中间移动，根据特定的条件确定指针移动的方向和步骤。

相向双指针法适用于以下情况：

排序数组：当数组已经排序（升序或降序）时，可以使用相向双指针法在有序数组中查找目标元素或确定满足某个条件的元素。通过将一个指针指向数组的起始位置，另一个指针指向数组的末尾位置，根据两个指针指向的元素的大小，可以确定指针移动的方向，从而缩小搜索范围。
有序数组求和问题：对于有序数组中求和的问题（如两数之和、三数之和），可以使用相向双指针法。通过将一个指针指向数组的起始位置，另一个指针指向数组的末尾位置，根据两个指针指向的元素的和与目标值的大小关系，确定指针移动的方向，从而逐步逼近目标值。
回文字符串判断：对于判断一个字符串是否为回文字符串的问题，可以使用相向双指针法。通过将一个指针指向字符串的起始位置，另一个指针指向字符串的末尾位置，比较两个指针指向的字符是否相等，并依次向中间移动指针，直到两个指针相遇或交叉。

相向双指针法通常用于解决需要从两个方向逼近问题解的情况，其中的关键在于确定指针移动的方向和步骤。在使用相向双指针法时，需要考虑指针移动的条件和遍历结束的条件，以及如何根据当前指针指向的元素或字符的情况来调整指针的移动。

数组双指针