尺取法（双指针）
这一讲我们来介绍一个非常常用的算法 —— 尺取法，一般称为双指针算法，下文也将用这种说法。这种算法应用场景挺广，在很多题目中只是作为解出题目的其中一个关键部件，下面我将给没接触过的小伙伴详细讲解，会从模板题入手，不会直接上综合题，这点大家放心~
原理
双指针算法是一个优化算法，注意解决一些区间相关的问题，它可以将一个双循环优化成一个单循环，即将 O(n2) 的时间复杂度讲到 O(n)，但并不是所有双循环都能优化成单循环，需要看应用的场景。
for(int i = 0; i < n; i++) //i从头扫到尾 for(int j = n-1; j >= 0; j--) //j从尾扫到头 { ... } //双指针优化后： for (int i = 0, j = n - 1; i < j; i++, j--) { ... }
最长连续不重复子序列
【题目地址】https://www.acwing.com/problem/content/801/
我们先来看第一道模板题，我会在讲题目的过程中给大家介绍双指针的用法，帮助大家能够更深刻的理解。
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼105 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤105
输入样例：
5 1 2 2 3 5
输出样例：
3
题目要求我们找到最长的不包含重复的数的连续区间长度，先来思考最暴力的做法，即需要枚举左右端点，根据左端点然后往后枚举右端点，直至出现重复的数为止。可以发现这种做法会出现大量的重复遍历，这时双指针算法就派上用场了，我们可以利用一个滑动窗口进行模拟，直接上步骤：
1.这里需要用到两个数组，一个数组 a 用来存储序列，一个数组 s 用来存储每个数字出现的次数，至于有何作用接着往下看。另外就是本题核心双指针算法，需要用到两个指针 i 和 j 来表示滑动窗口的右边界与左边界，初始时刻 i 和 j 都为 0。
2.可以边遍历边输入，为了方便大家理解，下面用一个例子带着大家模拟一遍，就拿题目样例举例，假设给定一个序列 {1, 2, 2, 3, 5}，然后开始模拟（下面图解中红色区域代表当前滑动窗口中的元素）。
第一步，输入第一个数 1，并令 s[a[i]]++ 即 s[1]++ 表示目前窗口当中 1 的个数加 1，然后发现此时窗口中并没有重复的元素，故更新窗口长度的最大值 res=max(res,i-j+1)=max(0,1)=1，然后将右边界指针 i 右移一位。
第二步，输入第二个数 2，与步骤一相同，统计对应更新对应数字的数量即 s[2]++ ，且没有重复元素出现，故更新窗口长度的最大值 res=max(res,i-j+1)=max(1,2)=2，然后将右边界指针 i 右移一位。
第三步，输入第三个数 2，同样令 s[2]++，发现加入的元素 2 窗口里已经出现过了，因为 s[2]>1 即元素 2 的数量已经大于 1。
这时候关键点就来了，我们要从窗口的左边界 j 开始删除元素，因为要保证序列是连续的。每次删除元素后都将对应 s[a[j]] 减去 1，即动态更新数组 s，直到发现 s[a[j]] 的值不大于 1 为止。
并更新窗口长度的最大值 res=max(res,i-j+1)=max(2,1)=2，然后将右边界指针 i 右移一位。
第四步，同上。发现没有重复元素，更新窗口长度的最大值。
第五步，同上。发现并没有重复元素，最终窗口长度的最大值更新为 3，结束遍历。
3.输出最长连续不重复子序列的长度，即窗口长度的最大值。
#include<bits/stdc++.h> using namespace std; const int N = 100010; int s[N], a[N], n; int main() { cin >> n; int res = 0; for (int i = 0, j = 0; i < n; i++) { cin >> a[i]; s[a[i]]++; while (s[a[i]] > 1) { s[a[j]]--; j++; } res = max(res, i - j + 1); } cout << res; return 0; }
数组元素的目标和
【题目地址】https://www.acwing.com/problem/content/802/
上面那题可以发现两个指针都是正向进行扫描即两指针扫描的方向一致，现在我们来看一道反向扫描的案例。
给定两个升序排序的有序数组 A 和 B，以及一个目标值 x。
数组下标从 00 开始。
请你求出满足 A[i]+B[j]=x 的数对 (i,j)。
数据保证有唯一解。
输入格式
第一行包含三个整数 n,m,x，分别表示 A 的长度，B 的长度以及目标值 x。
第二行包含 n 个整数，表示数组 A。
第三行包含 m 个整数，表示数组 B。
输出格式
共一行，包含两个整数 i 和 j。
数据范围
数组长度不超过 105。
同一数组内元素各不相同。
1≤数组元素≤109
输入样例：
4 5 6 1 2 4 7 3 4 6 8 9
输出样例：
1 1
注意题目给定的是两个有序的序列，这样就方便我们使用双指针算法。老样子先看暴力做法是什么，最暴力的就是先遍历数组 A 的元素，然后再对 A 中每个元素都遍历一遍 B 数组中的元素，然后输出元素之和为目标值 x 的数对。这样子做的时间复杂度为 O(n2)，而双指针算法就可以将改时间复杂度降为 O(n)，直接上步骤：
1.这里除了要用到两个数组 A 与 B 来存储元素外，还需要用到两个指针 i 和 j 分别指向数组 A 和 B 的元素。现在关键点来了，我们不能像上题一样让两个指针扫描同一方向，这样会漏掉很多情况，例如一个小值加上一个大值等于目标值。所以需要反向进行扫描，即指针 i 和 j 初始化时分别指向数组 A 的一个元素和数组 B 的最后一个元素。
2.现在开始进行扫描，指针 i 从前往后对数组 A 进行扫描，指针 j 从后往前对数组 B 进行扫描。这其实用到了有序序列的性质，可以保证我们不会漏掉任何一种情况，而扫描时判断的规则如下：
①让指针 i 固定往后走，即每一趟 i 都只往后移一位，然后根据 j 指向的值进行判断。
②如果 A[i]+B[j]>x，说明两指针指向的元素之和大于目标和，现在我们想要这个和更小一点，而指针 j 遍历的方向就是从大到小，故将指针 j 往前移直到元素之和小于等于目标和为止。
③如果此时元素之和等于目标值，则直接输出结果即可。反之，进行下一趟遍历即将指针 i 后移一位，因为此时元素之和已经小于等于目标值，我想获得不同的数对或让它更大一点，而指针 i 遍历的方向就是从小到大，故移动 i 最合适。
为了加深理解，还是拿题目样例进行模拟，假设给定两个有序数组 A = {1, 2, 4, 7} 和 B = {3, 4, 6, 8, 9}，以及一个目标值 x = 6。
首先，i=0 指向数组 A 的第一个元素，j=4 指向数组 B 的最后一个元素，然后进行判断，发现 1+9=10 大于目标值 6，故将指针 j 往前移动直至元素之和小于等于目标值。
发现此时元素之和 1+4=5 小于目标值 6，故将 i 往后移一位再重复上面的操作。
结果发现此时两指针指向的元素之和 2+4=6 等于目标值 6，故直接输出该数对的下标。后面继续上述操作，发现不再出现元素之和等于目标值的数对，结束遍历。
#include<bits/stdc++.h> using namespace std; const int N = 100010; int A[N], B[N], n, m, x; int main() { cin >> n >> m >> x; for (int i = 0; i < n; i++) scanf("%d", &A[i]); for (int i = 0; i < m; i++) scanf("%d", &B[i]); for (int i = 0, j = m - 1; i < n; i++) { while (j >= 0 && A[i] + B[j] > x) j--; if (j >= 0 && A[i] + B[j] == x) printf("%d %d\n", i, j); } return 0; }
