双指针¶
滑动窗口¶
滑动窗口是双指针的其中一种，因两个指针从同一侧出发距离一远一近而得名。滑动窗口用与求解具有单调性的连续子序列问题。比如下面这道习题：
例题
给定一个长度为 \(n\) 的正整数序列，要你找到一个最短的连续子序列，使得这个子序列的和正好大于等于 \(k\)。输出这个子序列的长度。
这是一个非常经典的双指针例题，但是同样可以由二分解决。因为我们可以发现，假设有一个判断函数 \(f(x)\) 表示有没有一个长度为 \(x\) 的子序列的和大于等于 \(k\)，那么 \(x\) 越大 \(f(x)=1\) 的可能性就越高，那么单调性不久来了吗？因此我们可以使用二分求解，时间复杂度 \(\mathcal O(n\log_2 n)\)。
但是这样子还不够优秀。我们发现，区间 \([l,r]\) 的和可以很快地转移到 \([l,r+1]\) 或 \([l+1,r]\) 的和，而且每一次左指针右移的时候，右指针都要往右移动若干个元素（可能不移动），那么这就代表我们可以直接枚举左指针，然后让右指针在上一个的基础上往右移动若干个元素，这样就可以实现 \(\mathcal O(n)\) 的算法。
注意我们的右指针一般在定义的时候表示的意思其实是当前选的数，因此右指针移动过后的序列实际上是 \([l,r)\)。并且在右指针移动完成后之后不一定会满足条件，所以我们需要在右指针移动完成后进行一次判断。
代码
for (int i = 1, j = 1; i <= n; i++) { // 枚举左指针
for (; j <= n && sum < k; sum += a[j++]) { } // 调整右指针
if (sum >= k) { // 判断是否满足要求
ans = min(ans, r - l); // 注意区间类型
}
sum -= a[i]; // 左指针右移
}
滑动窗口所能求解的题目一般都具有一下特征：
- 在一个序列里面找一个满足条件的最短子序列；
- 答案有单调性，越长的子序列可能越会得到答案；
- 区间 \([l,r]\) 可以较快地转移到 \([l+1,r]\) 和 \([l,r+1]\)；
对撞指针¶
对撞指针也是双指针的一种，一般是两个指针从两边开始不断向中间逼近，直到两个指针相遇。
例题
给定一个长度为 \(n\) 的有序整数数列，找到任意两个数和正好为 \(k\)。
这道题目跟上道题很相似，但是不同之处就是我们要求的是两个数，而不是一个子序列，而且数组也是排了序的。因此我们可以使用对撞指针来求解。
我们可以先枚举左指针，再枚举右指针，最后找到一个满足条件的答案即可。但是这样做时间复杂度就会达到 \(\mathcal O(n^2)\)。其实，滑动窗口跟对撞指针是有异曲同工之妙的，当我们将左指针向右移的时候，右指针肯定只能向左移若干个元素，因为这个数组是递增的，为了迎合左指针的变大，右指针就只能变小。这道题就可以使用 \(\mathcal O(n)\) 的算法来求解了。
代码
for (int i = 1, j = n; i < j; i++) {
for (sum += a[i]; j > i && sum > k; sum -= a[j--]) { }
if (sum == k) {
cout << i << ' ' << j << '\n';
}
}
快慢指针¶
快慢指针也是一种双指针算法，因为指针一快一慢而得名，一般用与判断环的问题当中。
例题
给定一个链表的头，你需要判断这个链表是否有环。
快慢指针可以用来判断一个链表是否有环。首先，我们定义两个指针，一个快指针，一个慢指针。快指针每次移动两个节点，慢指针每次移动一个节点。如果快指针能够追上慢指针，那么说明这个链表有环。
代码
for (LinkNode *slow = head, *fast = slow->next; fast != tail; slow = slow->next, fast = fast->next) {
if (fast == tail || fast->next == tail) {
return 0;
}
}
return 1;