尺取法(双指针、two pointers), 是竞赛中一个常用的时间复杂度优化技巧, 用来解决序列的区间问题，十分好用
问题模型
已知一个正整数序列a(0<ai<=1e4)，长度为n（n<=1e5）,从其中取出一段连续子序列，满足子序列之和不小于s(0<s<1e8),求子序列的最小长度为多少
方法一：纯暴力
按部就班直接模拟
1
2
3
4
5
6
7
8
9
10
for(int i=1; i<=n; i++) {
for(int j=i; j<=n; j++) {
int sum = 0;
for(int k=1; k<=n; k++) {
sum += a[k];
}
if(sum >= s)
ans = min(ans, j-i+1);
}
}
O（n^3），绝对TLE
方法二：前缀和+二分答案
采用前缀和预处理数据，可以省去求和循环，由于长度具有单调性且数据为正整数，所以可以二分长度，达到nlogn的时间复杂度
前缀和处理数据
使用一个sum数组，sum[i]表示 a[1] + a[2] + … + a[i] 的和，预处理的时间复杂度为O(n)，算和的时间复杂度为O(1)
举个例子：
| a[1] | a[2] | a[3] | a[4] | a[5] |
|---|---|---|---|---|
| 1 | 3 | 2 | 7 | 9 |
前缀和数组即为
| sum[1] | sum[2] | sum[3] | sum[4] | sum[5] |
|---|---|---|---|---|
| 1 | 1+3 | 1+3+2 | 1+3+2+7 | 1+3+2+7+9 |
比如求a[2]+…+a[5],即可表示为sum[5] - sum[2-1]
可以用以下操作实现前缀和：
1
2
for(int i=1; i<=n; i++)
sum[i] = sum[i-1] + a[i];
但是代码时间复杂度还是为O(n^2)，仍需优化
二分答案
由于区间长度具有单调性(0<=len<=n)，且ai均为正整数（为什么负数会出问题？自己想一想），所以可以二分子序列的长度，再来一个滑动窗口即可
这样若与前缀和搭配起来，时间复杂度为O（nlogn）
PS:实际上也可以不用前缀和，每次左右端点移动时进行加减操作也可以实现nlogn的复杂度，但是不如前缀和简洁，所以就没写了
下面是前缀和与二分法搭配的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
const int N = 1e5 + 100;
int n, s;
int a[N], sum[N];
bool check(int x) {
for(int i=1,j=x; j<=n; i++,j++) {
int tmp = sum[j] - sum[i-1];
if(tmp >= s) return true;
}
return false;
}
int main() {
cin >> n >> s;
for(int i=1; i<=n; i++) {
cin >> a[i];
sum[i] = sum[i-1] + a[i];
}
int l = 1, r = n;
while(l < r) {
int mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid + 1;
}
cout << l;
return 0;
}
O（nlogn）已经很优秀了，但是能优化成线性时间复杂度
方法三：尺取法
尺取法可以理解为一把不定长、不定位置的尺子，可以移动两端再数组中的位置。我们设当前尺子的两端分别为l、r，l和r的初值均为1（l<=r）
由于l和r都不是固定的，所以我们先将l固定，然后再对r进行操作。根据题意，我们应使r不停右移，直至满足a[l]+…+a[r]不小于s，之后，再将l右移，直至a[l]+…+a[r]小于s，期间不停更新ans
但是，这样就有一个问题：
如果l、r内，有另一区间(ls、rs, l<=ls<=rs<=r)，并且a[l]+…+a[r] > a[ls]+…+a[rs] >=s, 这时候怎么办？
实际上，要是有这么一个区间，再之前更新r的时候，r就会更新到rs的位置，因为这样答案肯定比更新到后面更小,之后l也会再右移时更新到ls的位置，所以不可能会出现如此情况
如果有ls、rs内的区间，也可以用以上方法来解释
由于尺取法稍难理解，所以建议多画画图
下面给出代码，其中含有注释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 尺取法代码
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 100;
int n, s;
int a[N], sum[N];
int ans = INF;
int main() {
cin >> n >> s;
for(int i=1; i<=n; i++) {
cin >> a[i];
sum[i] = sum[i-1] + a[i];
}
int i = 1, j = 1; // 两个指针起始状态都位于a[1]
while(i <= n) {
// 若a[i] + ... + a[j] < s, 更新j直至满足条件
while(sum[j] - sum[i-1] < s) {
j ++;
}
if(j > n) break; // 连j取到n都不满足条件，即可结束循环
ans = min(ans, j-i+1); // 更新答案
i ++; // 更新i，尽量使子序列长度小
}
cout << ans;
return 0;
}
时间复杂度O(n)，极其优秀
尺取法是一个需要熟练掌握的方法，建议大家多刷题练习，更充分地运用在比赛当中
CSP-J2021rp++!
