概要
雙指針是一種比較常見的算法思想，在循環(huán)遍歷數(shù)組時經(jīng)常會用到。雙指針主要有兩種算法技巧：1、快慢指針（例如已發(fā)推文中的LeetCode進(jìn)階-實戰(zhàn)之快慢指針（阿里面試題）），利用指針確定的相對位置關(guān)系，快指針先到達(dá)邊界的特點進(jìn)行搜索；2、雙向指針，雙向指針的特點兩指針分別從前往后和從后往前遍歷，本文介紹的正是這種用法。
原題
977. Squares of a Sorted Array (Easy)
Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.
Example 1:
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Example 2:
Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]
Note:
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.
977.有序數(shù)組的平方
給定一個按非遞減順序排序的整數(shù)數(shù)組 A，返回每個數(shù)字的平方組成的新數(shù)組，要求也按非遞減順序排序。
示例 1：
輸入：[-4,-1,0,3,10]
輸出：[0,1,9,16,100]
示例 2：
輸入：[-7,-3,2,3,11]
輸出：[4,9,9,49,121]
提示：
1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非遞減順序排序。
- 分類：雙指針
分析&&思路
根據(jù)題意，數(shù)組為非遞減順序，數(shù)組中可能存在負(fù)數(shù)和非負(fù)數(shù)。負(fù)數(shù)在數(shù)組中從左到右平方（絕對值）依次變小，正數(shù)從右到左平方（絕對值）依次變小。因此采用雙指針分別從左往右、從右往左對比交換。
偽代碼
1、new一個大小與入?yún)⒋笮∫恢碌膇nt數(shù)組；
2、聲明兩個指針下標(biāo)，從左往右的指針和從右往左的指針；
3、for循環(huán)，從數(shù)組尾下標(biāo)到起始下標(biāo)0
i.若從右往左正數(shù)絕對值較大則將較大絕對值的數(shù)平方放入數(shù)組末位，同時從右到左指針左移一位；
ii.若從左往右非正數(shù)絕對值較大則將較大絕對值的數(shù)放入數(shù)組末位，同時從左到右指針右移一位；
4、循環(huán)結(jié)束，返回新數(shù)組的平方數(shù)的有序數(shù)組；
編碼實踐
public int[] sortedSquares(int[] A) {
int n = A.length;
int[] result = new int[n];
int i = 0, j = n - 1;
for (int p = n - 1; p >= 0; p--) {
if (Math.abs(A[i]) > Math.abs(A[j])) {
result[p] = A[i] * A[i++];
} else {
result[p] = A[j] * A[j--];
}
}
return result;
}
結(jié)語
本篇介紹了雙指針中比較經(jīng)典的雙向指針的用法，相對簡單但是比較有代表性適合算法基礎(chǔ)入門。事實上雙向指針在很多經(jīng)典的算法思想中都有出現(xiàn)，典型的比如快速排序就有用到。最后，如果覺得本篇對你有所幫助，不妨關(guān)注走一波～祝周末愉快！
