双指针算法的类型

指向两个序列

例如归并排序

指向一个序列

例如快速排序

双指针算法的用途

双指针的基本模板

举个例子：
1、给定一个字符串数组，依次输出数组中的每个字符串，str=["abc","efg","hijk"]

2、最长连续不重复子序列

在这里，j表示i左边能到达的最远的没有重复数字的距离，并且随着i++，j也是++，绝对不可能--

双指针技巧总结

快慢指针

--主要解决链表中的问题，例如典型的判定链表中是否包含环
快慢指针一般都初始化指向链表的头结点head，前进时快指针fast在前，慢指针slow在后，巧妙的解决链表中的一些问题

1、判定链表中是否含环

单链表的特点是每个节点只知道下⼀个节点，所以⼀个指针的话⽆法判断链表中是否含有环的。
如果链表中不含环，那么这个指针最终会遇到空指针 null 表⽰链表到头了，这还好说，可以判断该链表不含环。

但是如果链表中含有环，那么这个指针就会陷⼊死循环，因为环形数组中没有 null 指针作为尾部节点。
经典解法就是⽤两个指针，⼀个跑得快，⼀个跑得慢。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；如果含有环，快指针最终会超慢指针⼀圈，和慢指针相遇，说明链表含有环。

2、已知链表中有环，返回这个环的起始位置

ListNode detectCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
    if (fast == slow) break;
}
    slow = head;
    while (slow != fast) {
    fast = fast.next;
    slow = slow.next;
 }
    return slow;
}

当快慢指针相遇，让其中一个指针指向头结点，然后让它们以心相通的速度前进，再次相遇时所在的节点位置就是环开始的位置

3、寻找链表中点

类似上面的思路，我们还可以让快指针⼀次前进两步，慢指针⼀次前进⼀步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。

如果链表的长度为奇数，slow正好在中间的位置，如果是偶数，就在中间偏右的位置

4、寻找链表的倒数第 k 个元素

让快指针先⾛ k 步，然后快慢指针开始同速前进。这样当快指针⾛到链表末尾 null 时，慢指针所在的位置就是倒数第 k个链表节点

左右指针

--主要解决数组（或字符串）中的问题，例如二分查找

1、二分查找

int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
 while(left <= right) {
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}

查找左边界

l := 0
r := len(nums) - 1
    for l < r {
        mid := l + r >> 1
        if nums[mid] >= target {
            r = mid
        }else {
            l = mid + 1
        }
    }
        return r

查找右边界

l = 0
r = len(nums) - 1
    for l < r {
        mid := l + r + 1 >> 1
        if nums[mid] <= target {
            l = mid 
        }else {
            r = mid - 1 
        }
    }
        return r

2、反转数组

void reverse(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
// swap(nums[left], nums[right])
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++; right--;
}
}

3、滑动窗口算法

这里有一个滑动窗口的基本框架，但凡用到滑动窗口的问题都可以用这个框架进行改编

/* 滑动窗⼝算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
 int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移⼊窗⼝的字符
char c = s[right];
// 右移窗⼝
right++;
// 进⾏窗⼝内数据的⼀系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗⼝是否要收缩
while (window needs shrink) {
// d 是将移出窗⼝的字符
char d = s[left];
// 左移窗⼝
left++;
// 进⾏窗⼝内数据的⼀系列更新
...
}
}
}