常見演算法技巧之——雙指針思想
常見演算法技巧之——雙指針思想
雙指針思想是指設置兩個指針解決一些演算法問題。一般用的比較多的就是去解決數組、鏈表類的問題，還有很耳熟能詳的二分查找問題。本文將根據自己平時做題的總結以及在網上看到的其他大佬的總結講解來討論一下雙指針的使用技巧。本文會根據我平時做題實時更新。
快慢指針
雙指針的快慢指針用法是我最開始理解的第一種用法。快慢指針一般用來解決鏈表的問題多一些。設置一快一慢兩個指針fast和slow，初始化指向鏈表表頭。
1、計算鏈表的中點
給定一個鏈表，要求返回該鏈表的中點節點。
設置兩個快慢指針，都從頭節點開始，快指針每次前進兩個節點，慢指針每次前進一個節點，當快指針到達鏈表末尾的時候，慢指針剛好到達中點的節點。
下圖中藍色指針表示快指針，橙色指針表示慢指針。
//函數中最後的判斷return有問題，直接return slow即可，這樣寫是為了區分奇偶不同的區別
public LinkedList mid (LinkedList head) {
LinkedList fast = head;
LinkedList slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
if (fast == null) { //說明有偶數個節點，此時慢指針指向的是中點靠右的節點
return slow;
} else { //fast.next == null，說明有奇數個節點，此時慢指針指的恰好是中點
return slow;
}
}
2、判斷鏈表中是否有環
如果已知一個單鏈表的表頭，判斷該鏈表中是否含有一個環。通常單鏈表都是一個節點只指向下一個節點這樣的鏈式結構，如果只有一個指針，從頭節點開始一路next，如果碰到null則表示有環，但如果沒有環則會一直在環里打轉，所以單指針很難解決這樣的問題。
設置雙指針，兩個指針一快一慢，按照不同的速度從頭節點開始往下遍歷，如果最後兩個指針相遇則表示有環，如果沒有相遇，而是快指針先到了null則表示沒有環。
public boolean hasCycle (LinkedList head) {
LinkedList fast = head;
LinkedList slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) { //最後兩指針相遇，表示有環
return true;
}
}
return false; //若兩指針不相等，則說明快指針到了null
}
3、如果鏈表中有環，返迴環的起始位置
如果已知一個鏈表中含有環，要找出環的位置，返迴環的起始節點。
按照2中所說兩個指針相遇的時候說明這個鏈表中有環，那麼既然快指針速度是慢指針速度的二倍，那麼假設兩個指針第一次相遇的時候慢指針走了k步，則快指針就走了2k步，那麼快指針的路程減去慢指針的路程就是環的長度，即為k。
那此時假設環的起點距離兩指針的相遇點的距離為m，則從開始相遇點繼續往下走，直到再次達到環起點，一共走了k-m步，而之前假設慢指針走了k步，從開始到第一次相遇，慢指針是從鏈表表頭到第一次相遇點，走了k步，那麼慢指針從表頭到環的起點位置的距離也應該是k-m步（因為環起點距離相遇點是m步）。因此當兩指針第一次相遇的時候，將一個指針重新置到頭節點，然後兩個步調一致，同樣速度，每次前進一步，當再次相遇的時候，相遇位置就是環的起點。
4、求鏈表中環的長度
這個很簡單，當兩個指針第一次相遇的時候，保持快指針不動，讓慢指針繼續跑，兩指針再次相遇的時候慢指針跑的距離就是環的長度。
5、求鏈表倒數第k個節點
先讓某個指針走k步，然後兩個指針同時走，當前面的指針走到末尾的時候，後面的指針呢恰好走到倒數第k個節點。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head;
ListNode slow = head;
while (k > 0) {
--k;
fast = fast.next;
}
while (fast!=null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
左右指針
也有叫做碰撞指針的，通常需要一個有序的數組，左右兩個指針其實就是指示數組的下標，通常一個初始化在開頭，一個初始化在結尾。
1、二分查找
這個是很經典的例子，在有序的數組中查找某個數（記為x），返回下標。
剛開始兩個指針一前一後，判斷兩指針最中間的元素是否為查找的元素x，若是直接返回，如果不是且小於x，則將左指針移動到中間位置+1，即(l+r)/2 + 1，若大於x，則將右指針移動到中間位置-1。
public int BinarySearch (int[] nums, int target) {
int l = 0, r = nums.length-1;
while (l < r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return -1; //表示未找到
}
2、n數之和的問題
這裡以leetcode上的一個兩數之和的題為例為例，如果是三數之和可以轉化為一個數與兩數之和的和的問題。
兩數之和
給定一個整數數組 nums 和一個目標值 target，請你在該數組中找出和為目標值的那 兩個 整數，並返回他們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，數組中同一個元素不能使用兩遍。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/two-sum
先對數組排序，設置頭尾兩個指針，判斷相加之後與目標數的大小，如果相加之後大於目標，則移動右指針，讓右指針往左滑動，使得和更小，反之則讓左指針向右滑動，直到等於target。
但需要注意這道題給的並不一定是有序數組，所以並不能使用這個方法，但可以作為一個引例來啟發我們，假設數組是有序的。
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
Arrays.sort(nums);
int l = 0, r = nums.length - 1;
while (l < r) {
if (nums[l] + nums[r] == target) {
return new int[] {l,r};
} else if (nums[l] + nums[r] < target) {
l = l + 1;
} else {
r = r - 1;
}
}
return new int[] {-1,-1};
}
三數之和
給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有滿足條件且不重複的三元組。
注意：答案中不可以包含重複的三元組。
示例：
給定數組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/3sum
正如前文所說，可以將三數之和轉化為兩數與一個數之和，因為要三數之和為0，先給定一個數，則另外兩個數之和就得等於這個數的相反數。則可以將這兩個數的和轉化為上述的兩數之和問題。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
//剪枝，如果這個數和前一個數相等，那麼由此得到的答案必和前面重複
if (i > 0 && nums[i] == nums[i-1])
continue;
int target = -nums[i]; //b+c = target
int k = nums.length-1;
for (int j = i+1; j < nums.length; j++) {
if (j > i+1 && nums[j] == nums[j-1]) //j > i+1 保證了j指針至少挪動了一次
continue;
while (j < k && nums[j] + nums[k] > target) {
k--;
}
if (j == k) { //j和k的指針重合後，沒有一個k可以滿足a+b+c=0 && j<k
break;
}
if (nums[j] + nums[k] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
res.add(list);
}
}
}
return res;
}
}
四數之和
給定一個包含 n 個整數的數組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重複的四元組。
注意：
答案中不可以包含重複的四元組。
示例：
給定數組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
滿足要求的四元組集合為：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/4sum
繼續類比前面的三數之和，不過是多了層循環而已，利用雙循環先確定兩個數，然後剩下的兩個數就又變成了兩數之和的問題，但這類問題因為有重複的元素所以要注意剪枝去掉重複的答案，還有就是數組必需有序。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i <= nums.length-4; i++) {
if (i>0 && nums[i] == nums[i-1])
continue;
for (int j = i+1; j <= nums.length-3; j++) {
int tar = target - nums[i] - nums[j];
if (j>i+1 && nums[j] == nums[j-1])
continue;
for (int l = j+1; l <= nums.length-2; l++) {
if (l>j+1 && nums[l] == nums[l-1])
continue;
int r = nums.length-1;
while (r > l && nums[l] + nums[r] > tar)
r--;
if (r == l) {
break;
}
if (nums[l] + nums[r] == tar) {
List<Integer> res = new ArrayList<>();
res.add(nums[i]);
res.add(nums[j]);
res.add(nums[l]);
res.add(nums[r]);
result.add(new ArrayList<>(res));
}
}
}
}
return result;
}
}
3、反轉數組
將一個數組進行反轉，只需要設置好前後兩個指針，一個初始化指頭，另一個初始化指尾，然後交換兩個指針指向的內容，然後前面的指針+1，後面的指針-1，直到兩指針相遇（數組大小為奇數），或者兩指針相差1（數組大小為偶數）。
public void reverse (int[] nums) {
int l = 0, r = nums.length-1;
while (l < r) {
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
l++;
r--;
}
}
滑動窗口
其實滑動窗口應該也是左右指針中的一種，但因為它相對來說難以理解，所以單獨拎出來做一討論。
滑動窗口大概理解起來很簡單，但就是自己動手寫的時候會遇到很多問題，正所謂熟能生巧，筆者也才開始練這些演算法題，希望記錄下學習的過程。
1、無重複字元的最長子串
滑動窗口就是維護一個窗口，然後根據題目和新遇到的情況不斷更新這個窗口，不斷優化可能的解。舉個例子，比如leetcode上的無重複字元的最長子串問題。
給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。
示例 1:
輸入: "abcabcbb"
輸出: 3
解釋: 因為無重複字元的最長子串是 "abc"，所以其長度為 3。
示例 2:
輸入: "bbbbb"
輸出: 1
解釋: 因為無重複字元的最長子串是 "b"，所以其長度為 1。
示例 3:
輸入: "pwwkew"
輸出: 3
解釋: 因為無重複字元的最長子串是 "wke"，所以其長度為 3。
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/longest-substring-without-repeating-characters
利用滑動窗口可以完美的解決這個問題，用左指針指示窗口的最左端，右指針指示窗口的最右端，初始左指針指示第0個元素，右指針指示-1，定義一個set集合存儲當前解（即當前窗口中包含的字元），然後開始一直移動右指針，使其向右移動，直到碰到一個已經添加到當前解中的字元，這時記錄下當前的set的大小為當前最優解，然後將左指針向右移動一個，並在當前解set中移出窗口最左邊的字元。之後就是繼續移動右指針，更新當前解，每次右指針碰到當前解中已存在的字元時，判斷一下當前解的大小，如果比之前的最優解更優，則更新，反之不更新，繼續移出窗口中最左邊的字元，然後繼續重複上述操作，直到右指針到達字元串末尾。
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> ss = new HashSet();
//定義右指針
int res = 0, r = -1;
for(int i = 0; i < s.length(); i++) {
if (i != 0) {
ss.remove(s.charAt(i-1)); //去掉上次最左邊的元素
}
while (r+1 < s.length() && !ss.contains(s.charAt(r+1))) {
ss.add(s.charAt(r+1));
++r; //移動右指針
}
res = Math.max(res,r-i+1); //上次的最優和這次的最優進行對比，每次子串的開頭不一樣
if (r == s.length()-1) {
//r右指針已經到了最右邊，所以直接break出來，因為後面不會再有向當前解中增加元素，只會慢慢彈出當前解的元素，所以不必再繼續
break;
}
}
return res;
}
}
2、最小覆蓋子串
給你一個字元串 S、一個字元串 T 。請你設計一種演算法，可以在 O(n) 的時間複雜度內，從字元串 S 裡面找出：包含 T 所有字元的最小子串。
示例：
輸入：S = "ADOBECODEBANC", T = "ABC"
輸出："BANC"
提示：
如果 S 中不存這樣的子串，則返回空字元串 ""。
如果 S 中存在這樣的子串，我們保證它是唯一的答案。
來源：力扣（LeetCode）
鏈接：//leetcode-cn.com/problems/minimum-window-substring
1. 這道題利用滑動窗口也可以很優雅的解決，還是先初始化兩個指針l = 0, r = 0指向字元串S，開始先向右移動右指針使得窗口增大，而右指針停止移動的條件是當前左指針到右指針，即窗口內已經包含了字元串T，接著開始向右移動左指針，使得窗口儘可能的小，但要確保窗口中始終是包含字元串T的，等到左指針移動到不能再移動的時候，也就是若左指針再移動一次，則窗口中將不能包含字元串T的所有字元。這時的窗口是當前解，也就是當前最優解。
2. 將其保存下來，之後向右移動一下左指針，使得窗口中不再包含T的所有字元，也就是移出去了一個T中的字元，繼續向右移動右指針使其擴張，直到窗口再次包含了字元串T，然後繼續移動左指針直到窗口最小，比較當前解和前面的最優解，保存下更優的。
3. 接下來就是重複操作2，直到右指針到最後一個字元後，再移動左指針，得到窗口最小的時候的解，並繼續比較之前的最優解，保存更優的。
上面大概寫完滑動的過程，再來說說針對這個題，實現的時候的一些細節。
- 維護一個needs數組，保存T字元串每個字元出現的次數，再維護一個window數組，保存當前窗口中各個字元的數量，後面可以根據這兩個數組判斷當前窗口是否包含了字元串T
- 使用一個count變數，如果當前字元屬於T，而且窗口中還沒有足夠多的這個字元就說明這個字元目前對於窗口來說是必要的，那麼把這個字元加入窗口後給count++，如果窗口中已經有了足夠的這個字元，那將其加入窗口後無需給count++。而當將一個字元移出窗口時，如果移出了這個字元，窗口不再包含T的所有字元，就說明這個字元目前對於窗口來說也是必要的，那移出後給
count--，如果不是必需的則不需要減小count。這樣維護下來的一個count可以指示當前窗口是否完整包含了字元串T，如果count的大小等於T的長度就說明此時的窗口完整的包含了T，這樣就可以快速判斷窗口是否包含T，節省了程式執行時間。
//給出的示例題解中用curr代替了window，curr記為current，表示當前的窗口
class Solution {
public String minWindow(String s, String t) {
if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
return "";
}
int l = 0, r = 0; //定義左右指針
int size = Integer.MAX_VALUE; //窗口大小
int ans_l = 0; //最優情況下左邊的指針
int count = 0;
//下面needs和curr的下標是字元的ASCII碼值
int[] needs = new int[255]; //需要的
int[] curr = new int[255]; //現有的
for (int i = 0; i < t.length(); i++) { //初始化needs
needs[t.charAt(i)]++;
}
while (r < s.length()) {
char c = s.charAt(r); //當前右指針指的字元
if (needs[c] != 0) { //需要這個字元
if (curr[c] < needs[c]) { //這個字元對於目前窗口是必需的
count++;
}
curr[c]++;
}
r++;
while (count == t.length() && l < r) {
if (size > r-l) {
ans_l = l;
size = r-l;
}
char c1 = s.charAt(l);
if (needs[c1] > 0) {
if (curr[c1] == needs[c1]) { //這個字元對於目前窗口來說是必需的
count--;
}
curr[c1]--;
}
l++;
}
}
return size==Integer.MAX_VALUE?"": s.substring(ans_l,ans_l+size);
}
}
