雙指針

雙指針用于處理數組和鏈表等線性結構。同時用2個指針遍歷有序的數據結構，減少時間復雜度。

leetcode167 兩數之和

分析

由于數組是有序的，因此兩個指針，一個從前向后遍歷，一個從后往前遍歷，可以在O(n)時間復雜度完成查詢。
假設結果為[i, j]。那么左指針遍歷到i時，如果右指針大于j，那么和偏大，右指針左移，不會出現左指針右移的情況。直到右指針走到j，返回結果。右指針遍歷到j也是同理，因此不會出現左指針大于i，右指針小于j的情況。

題解

class Solution {public int[] twoSum(int[] numbers, int target) {int first = 0; // 第一個指針int last = numbers.length - 1;  // 第二個指針while (first < last) {int sum = numbers[first] + numbers[last];if (sum == target) {return new int[]{first + 1, last + 1};} else if (sum < target) {first++;} else {last--;}}return new int[]{-1, -1};}
}

leetcode88 合并兩個有序數組

分析

2個有序數組，每個數組用一個指針遍歷。因為合并結果存在nums1數組，而nums1數組的前半部分有值，后半部分是空的。所以與正向雙指針相比，逆向雙指針更快。

題解

class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int tail = m + n - 1;int i = m - 1; // 第一個指針int j = n - 1; // 第二個指針int cur;while (i >= 0 || j >= 0) {if (i < 0) {cur = nums2[j];j--;} else if (j < 0) {cur = nums1[i];i--;} else if (nums1[i] > nums2[j]) {cur = nums1[i];i--;} else {cur = nums2[j];j--;}nums1[tail] = cur;tail--;}}
}

leetcode142 環形鏈表

分析

假設slow指針和fast指針均從head節點出發，每次slow移動1個節點，fast移動2個節點。它們相遇時的位置如圖。a表示頭節點到入環點的距離，b表示入環點到相遇點的距離，c表示相遇點到入環點的距離。
slow = a + b, fast = a + n(b + c) + b
其中n表示fast節點在環中多走的次數。
fast = 2 * slow，則
a + n(b + c) + b = 2(a + b)，變換得到
(n - 1)(b + c) + c = a，這個等式意味著，分別從相遇點出發和從頭結點出發的兩個節點終會在入環點相遇。

非公式分析

現在fast和slow在相遇點相遇，slow走過的距離是x。此時再來一個節點ptr以slow的速度從頭結點走到相遇點，走過的距離也是x。那么slow在這期間走過的距離是多少？是2x，恰好是之前fast走過的距離。ptr與slow相遇的位置恰好是slow與fast相遇的位置。
由于slow與ptr在環里相遇，它們速度又相同，因此它們在環里的每個位置都相遇，自然包括入環點。

題解

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (fast != null && fast.next != null) {fast = fast.next.next; // 快指針slow = slow.next;  // 慢指針if (slow == fast) {fast = head; // 不浪費指針，fast表示ptrwhile (fast != slow) {fast = fast.next;slow = slow.next;}return fast;}}return null;}
}

leetcode76 最小覆蓋子串

分析

左右指針在同一個字符數組上，分別表示子串的左右邊界。由于要求最小子串，因此先用右指針保證覆蓋子串內容，再停止右指針并用左指針壓縮子串范圍。

題解

    public static String minWindow(String s, String t) {char[] sArray = s.toCharArray();char[] tArray = t.toCharArray();int[] cnt = new int[128];int count = 0;for (char c : tArray) {cnt[c]++;count++;}int start = -1;int end = sArray.length;int l = 0;for (int r = 0; r < sArray.length; r++) {if (--cnt[sArray[r]] >= 0) {count--;}while (count == 0) {if (++cnt[sArray[l]] > 0) {if (r - l < end - start) {end = r;start = l;}count++;}l++;}}return start == -1 ? "" : s.substring(start, end + 1);}
}