1. 解释
其实双指针算法，并不是一种具体的公式或者范式。而是一种思路。一种节省时间运算的思路。
通常是指通过设置两个指针不断进行单向移动来解决问题的形式。
双指针算法的核心用途就是：优化时间复杂度
而我们经常使用双指针的场景就是两层循环。
指针，其实就代表了我们循环过程中的下标值。
我们讲了，双指针只是一种思路。而针对某些场景大家使用双指针总结了一些通用范例。
- 左右指针：创建两个指针（变量），一个指向开头，一个指向末尾，然后向中间遍历，直到满足条件或者两个指针相遇；
- 快慢指针：常见于链表查询中。创建两个指针，开始都指向开头，根据条件不同，快指针走得快，慢指针走的慢，直到满足条件或者快指针走到结尾；
- 滑动窗口：进行单调性的子串问题。创建两个指针，两个指针包裹的范围叫做窗口，然后通过移动指针，匹配窗口中的条件是否满足要求。
下面针对这几种范例场景，进行简单学习和了解。
2. 左右指针
通常，我们在有序数组中使用左右指针的情况较多。
例如：我们有一个数组nums，我们要找其中某个值。那么我们使用的二分查找，就是所谓的左右指针了。
代码语言：javascript复制public int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;//搜索区间为[left,right] ,就是两个指针了
while (left <= right) {//设定终止条件。
int mid = left (right - left) / 2;//不用mid=(left right)/2 是为了防止left right溢出>Integer.Maxvalue就会边为负数
if (nums[mid] < target) {
left = mid 1;//缩小左边界，区间[mid 1，right]， 也就是指针移动
} else if (nums[mid] > target) {
right = mid - 1;//缩小右边界，区间[left,mid-1]， 也就是指针移动
} else {
return mid;//搜索到目标区间，nums[mid]=target，return mid
}
}
return -1; //遍历数组没有找到target
}3. 快慢指针
比较常见的情况就是在链表中进行查询处理。例如我们要判断一串链表数据中，有没有环。
也就是某个链表的值是前面链表的值。例如下图所示：
示例代码：
代码语言：javascript复制public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}快慢指针一般都初始化指向链表的头结点head，前进时快指针fast在前，慢指针slow在后，巧妙解决一些链表中的问题。
上面的示例只是简单的情况，我们还可以使用快慢指针，实现查找链表中指定倒数第N个元素的值。
将快指针值，先加上指定N步。然后让快慢指针开始同速前进，当快指针走到末尾null。那么慢指针指向的就是我们的要求了。
4. 滑动窗口
这个概念的命名可以说是很直观了，通过两个指针指向的元素之间形成的一个窗口，然后我们滑动这个窗口进行数据比对。直到满足要求的数据为止。
而这个窗口分两种，一种是固定大小的窗口，一个是大小动态变化的窗口。
而应用场景和要求：
- 一般给出的数据结构是数组或者字符串
- 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
- 该问题本身可以通过暴力求解
例如 无重复字符的最长子串 的示例：
代码语言：javascript复制 public int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
for (int i = 0; i < n; i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.remove(s.charAt(i - 1));
}
while (rk 1 < n && !occ.contains(s.charAt(rk 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk 1));
rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i 1);
}
return ans;
}就是一个典型的利用滑动窗口的思路，来实现的算法。
