??雙指針，指的是在遍歷對(duì)象的過(guò)程中元莫，不是普通的使用單個(gè)指針進(jìn)行訪問(wèn)赖阻。而是使用兩個(gè)指針采用不同的方式進(jìn)行移動(dòng)，從而達(dá)到我們的目的踱蠢。

單指針.png

1.快慢指針
2.固定間距指針
3.對(duì)撞指針
下面榆浓，我將針對(duì)這三種用法來(lái)舉例說(shuō)明。

1.快慢指針

??快慢指針指兩個(gè)指針步長(zhǎng)不同撕攒。
??經(jīng)典用法就是用于檢測(cè)鏈表是否有環(huán)陡鹃，例如LeetCode 141 Easy 環(huán)形鏈表烘浦。這道題我們除了可以用HashSet判斷一個(gè)節(jié)點(diǎn)是否被訪問(wèn)過(guò)以外，也可以用快慢指針來(lái)解決:如果鏈表存在環(huán)萍鲸，那么快指針終將追上慢指針闷叉。
??題目描述和官方解法如下:

LeetCode 141 環(huán)形鏈表

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    ListNode slow = head;
    ListNode fast = head.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

2.固定間距指針

??兩個(gè)指針距離一定的距離，步長(zhǎng)相同
??經(jīng)典用法就是用于解決滑動(dòng)窗口脊阴，或者一次遍歷獲取鏈表的倒數(shù)第n個(gè)節(jié)點(diǎn)問(wèn)題握侧，例如LeetCode 19 Easy 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
我們可以使用兩個(gè)指針而不是一個(gè)指針。第一個(gè)指針從列表的開(kāi)頭向前移動(dòng) n+1 步嘿期，而第二個(gè)指針將從列表的開(kāi)頭出發(fā)∑非妫現(xiàn)在，這兩個(gè)指針被 nn 個(gè)結(jié)點(diǎn)分開(kāi)备徐。我們通過(guò)同時(shí)移動(dòng)兩個(gè)指針向前來(lái)保持這個(gè)恒定的間隔孽查，直到第一個(gè)指針到達(dá)最后一個(gè)結(jié)點(diǎn)。此時(shí)第二個(gè)指針將指向從最后一個(gè)結(jié)點(diǎn)數(shù)起的第 nn 個(gè)結(jié)點(diǎn)坦喘。我們重新鏈接第二個(gè)指針?biāo)玫慕Y(jié)點(diǎn)的 next 指針指向該結(jié)點(diǎn)的下下個(gè)結(jié)點(diǎn)盲再。
??題目描述和官方解法如下:

LeetCode 19 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
    // Advances first pointer so that the gap between first and second is n nodes apart
    for (int i = 1; i <= n + 1; i++) {
        first = first.next;
    }
    // Move first to the end, maintaining the gap
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    second.next = second.next.next;
    return dummy.next;
}

3.固定間距指針

??兩個(gè)指針從頭尾相向遍歷
??經(jīng)典用法就是用于解決二分查找問(wèn)題，或是n數(shù)之和等一系列問(wèn)題瓣铣。例如LeetCode 1答朋，LeetCode 15，LeetCode 18棠笑，這三道的難度分別是Easy运悲，Easy矾瑰，Medium，雖然難度是遞增的，但是其解法的中心思想一直沒(méi)變：對(duì)于有序數(shù)組竭宰，使用頭尾兩個(gè)指針雨膨，使用sum和target進(jìn)行比對(duì)留量，遍歷整個(gè)數(shù)組吼具。這里直接舉LeetCode 18 四數(shù)之和這個(gè)例子吧，其他太簡(jiǎn)單从橘。 四數(shù)之和
??題目描述和我個(gè)人的解法如下:

LeetCode 18 四數(shù)之和

 public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 4) {
            return res;
        }

        int size = nums.length;
        Arrays.sort(nums);

        for (int i = 0; i < size - 3; i++) {

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int min = nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3];
            int max = nums[i] + nums[size - 3] + nums[size - 2] + nums[size - 1];
            if (min > target) {
                break;
            }
            if (max < target) {
                continue;
            }

            for (int j = i + 1; j < size - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }

                int left = j + 1;
                int right = size - 1;

                int minSub = nums[i] + nums[j] + nums[left] + nums[left + 1];
                int maxSub = nums[i] + nums[j] + nums[right] + nums[right - 1];
                if (minSub > target) {
                    continue;
                }
                if (maxSub < target) {
                    continue;
                }

                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[right] + nums[left];
                    if (sum == target) {
                        res.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return res;
    }