【算法模板】基础：尺取法

尺取法（Sliding Window Technique），也叫滑动窗口法，是一种常见的算法思想，主要用于在一维数组或字符串中寻找满足某种条件的子数组或子串。它的核心思想是通过维护一个可变的窗口来遍历数组或字符串，从而有效地减少问题的时间复杂度。

算法思想

尺取法的核心思想是：

1. 维护一个窗口：在数组或字符串上维护一个固定或可变的窗口，这个窗口可以看作是两个指针（通常是 left 和 right），用来表示当前关注的子数组或子串。
2. 扩大或缩小窗口：通过移动 right 指针来扩大窗口的右边界，通过移动 left 指针来缩小窗口的左边界，从而动态调整窗口的大小。
3. 检查窗口内容：在每次调整窗口时，检查当前窗口是否满足问题的条件。如果满足，则记录或进一步处理；如果不满足，则继续调整窗口的大小或位置。

算法流程

以在数组中寻找和为某个目标值的最短子数组为例，尺取法的算法流程如下：

1. 初始化：
   • 定义两个指针 left 和 right，都指向数组的起始位置。
   • 定义一个变量 current_sum 来存储当前窗口内元素的和。
   • 定义一个变量 min_length 来存储最短子数组的长度，初始值设置为正无穷大。
2. 移动右指针：
   • 逐步移动 right 指针，将 right 指向的元素加入 current_sum 中。
   • 每次移动后，检查 current_sum 是否大于或等于目标值。如果是，则尝试缩小窗口。
3. 移动左指针：
   • 当 current_sum 大于或等于目标值时，逐步移动 left 指针，将 left 指向的元素从 current_sum 中移除。
   • 每次移动后，检查 current_sum 是否仍然大于或等于目标值。如果是，则继续缩小窗口，并更新 min_length。
   • 如果 current_sum 小于目标值，则停止移动 left 指针，并回到移动 right 指针的步骤。
4. 结束：
   • 当 right 指针遍历完整个数组后，算法结束。如果 min_length 仍为正无穷大，说明不存在满足条件的子数组；否则，返回 min_length 作为结果。

例题

字符串 (nowcoder.com)

小N现在有一个字符串S。他把这这个字符串的所有子串都挑了出来。一个S的子串T是合法的，当且仅当T中包含了所有的小写字母。小N希望知道所有的合法的S的子串中，长度最短是多少。

#include <bits/stdc++.h>
using namespace std;int main(){string s;cin>>s;const int n=s.size();int ans=0;for(int i=0;i<n;i++){while(i<n and not islower(s[i]))i++;int len=1;while(i+len<n and islower(s[i+len]))len++;i+=len-1;ans=max(ans,len);}cout<<ans<<endl;return 0;
}

丢手绢 (nowcoder.com)

“丢_丢丢手绢，轻轻地放在小朋友的后面，大家不要告诉她，快点快点抓住她，快点快点抓住她。”牛客幼儿园的小朋友们围成了一个圆圈准备玩丢手绢的游戏，但是小朋友们太小了，不能围成一个均匀的圆圈，即每个小朋友的间隔可能会不一致。为了大家能够愉快的玩耍，我们需要知道离得最远的两个小朋友离得有多远（如果太远的话牛老师就要来帮忙调整队形啦！）。

因为是玩丢手绢，所以小朋友只能沿着圆圈外围跑，所以我们定义两个小朋友的距离为沿着圆圈顺时针走或者逆时针走的最近距离。

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;vector<int> v(n);for (int &i : v) cin >> i;int sum = accumulate(v.begin(), v.end(), 0);int l = 0, r = 0, s = 0;int ans = 0;for(int l = 0,r=0;l < n; l++){while(s < sum/2)s+=v[(r++)%n];ans=max(ans,min(sum-s,s));s-=v[l];}cout << ans << endl;return 0;
}