一、雙指針-數組 相關題型與常用思路

1、單個數組

（1）原地移除元素類

? ? ? ? 如推薦習題中的（1）、（2）、（3），都屬于此類。引入雙指針 pre、last ，用 pre 指針表明數組的最后位置；用 last 指針結合 for 遍歷數組，去尋找不符合題意的元素，將其插入有效數組中，也就是 pre 位置，從而達到原地處理的要求。

????????以題（2）為例：

class Solution {public int removeDuplicates(int[] nums) {//慢指針：指向最終數組的最后元素int low = 0;//在比較中將第一個元素視為不同元素int res = 1;//快指針從1開始，因為要默認保存第一個元素，后面的元素再進行比較for(int fast = 1; fast < nums.length; fast++){//若重合，則過濾不保存;除非不重合，則保存該元素if(nums[fast] != nums[low]){res++;low++;nums[low] = nums[fast];}}return res;}
}

（2）特殊規則處理元素

? ? ? ? 如推薦習題中的（5），若要實現時間復雜度為 O(n)，必然是使用雙指針的。用雙指針從數組的兩側往中間位置移動，直到遍歷完所有元素。

class Solution {public int[] sortedSquares(int[] nums) {int len = nums.length;int[] res = new int[len];int i,j,x;i = 0;j = len - 1;x = len - 1;//從兩端往中間依次判定while(i <= j){if(Math.abs(nums[i]) >= Math.abs(nums[j])){res[x] = nums[i] * nums[i];i++;}else{res[x] = nums[j] * nums[j];j--;}x--;}return res;}
}

（3）滑動窗口--待補充

2、兩個數組

????????一定規則下，比較兩數組之間的關系，大多是相等關系。

????????如推薦習題中的（4），若要實現時間復雜度為 O(m+n)，必然是使用雙指針的。結合提意，此題需要從尾部開始遍歷，遇見特殊字符時，做好標記，以便直接跳過后續的字符。

class Solution {public boolean backspaceCompare(String s, String t) {int sLen = s.length();int tLen = t.length();int p1 = sLen - 1;int p2 = tLen - 1;int skipS = 0;int skipT = 0;//倒序處理字符串while(p1 >= 0 || p2 >= 0){while(p1 >= 0){if(s.charAt(p1) == '#'){    //  為退格符，則增加退格符數量skipS++;p1--;}else{                      if(skipS > 0){           //  為字母，且退格符數量為正數，則減少退格符數量   skipS--;p1--;}else{                  //  為字母，且退格符數量為0，則退出當輪循環break;}}}while(p2 >= 0){if(t.charAt(p2) == '#'){    //  為退格符，則增加更退格符數量skipT++;p2--;}else{                      if(skipT > 0){          //  為字母，且退格符數量為正數，則減少退格符數量  skipT--;p2--;}else{                  //  為字母，且退格符數量為0，則退出當輪循環break;}}}if(p1 >= 0 && p2 >= 0){         //對比兩個字符串中有效字符是否相同if(s.charAt(p1) == t.charAt(p2)){p1--;p2--;}else{return false;} }else if(p1 < 0 && p2 >= 0 || p1 >= 0 && p2 < 0){   //或有一方已為空，而另一方不為空【若不處理會導致死循環！！】return false;}}if(p1 > 0 || p2 > 0){               //若經過上述比較，仍然存在至少一方不為空，則表明兩字符不相同return false;}return true;}
}

二、推薦習題

（1）原地 移除元素

????????27.移除元素

????????給你一個數組?nums?和一個值?val，你需要?原地?移除所有數值等于?val?的元素。元素的順序可能發生改變。然后返回?nums?中與?val?不同的元素的數量。

????????假設?nums?中不等于?val?的元素數量為?k，要通過此題，您需要執行以下操作：

• 更改?nums?數組，使?nums?的前?k?個元素包含不等于?val?的元素。nums?的其余元素和?nums?的大小并不重要。
• 返回?k。

（2）原地 刪除有序數組的重復項

????????26.刪除排序數組中的重復項

????????給你一個?非嚴格遞增排列?的數組?nums?，請你?原地?刪除重復出現的元素，使每個元素?只出現一次?，返回刪除后數組的新長度。元素的?相對順序?應該保持?一致?。然后返回?nums?中唯一元素的個數。

????????考慮?nums?的唯一元素的數量為?k?，你需要做以下事情確保你的題解可以被通過：

• 更改數組?nums?，使?nums?的前?k?個元素包含唯一元素，并按照它們最初在?nums?中出現的順序排列。nums?的其余元素與?nums?的大小不重要。
• 返回?k?。

（3）原地 移除目標值到數組末尾

????????283.移動零

（4）比較有效字符串

????????844.比較含退格的字符串

（5）對有序數組元素的平方值，形成新有序數組

????????977.有序數組的平方