双指针算法实战：唯一的雪花、逛画展、字符串与丢手绢

2.2 逛画展

2.2.1 题目

链接：逛画展

2.2.2 算法原理

（1）进窗口：right 位置元素记录到统计次数的哈希表中，如果次数是 0 变 1，说明窗口内多了「一种」字符，记录一下； （2）判断：当窗口内字符种类等于 m 时，窗口合法，right 停止右移，接下来需要出窗口； （3）出窗口：让 left 所指位置的元素在哈希表中的次数减一，如果次数是 1 变 0，说明窗口内少了「一种」字符，记录一下； （4）更新结果：在判断成立时，窗口合法，此时更新窗口的大小。

综上：变引出此题答案的多种处理方式也是笔者在做此题遇到的一些坑点分享给大家 (1) 因为此题要输出区间的左右下标故第一种想法便是用两个变量 x 和 y 去记录但初始化会遇到怎么样去赋初值这是会影响结果的：如果使用一个 ret 来记入结果： 第一种情况：ret = n 那么 x 等于 1，y = n；否则在极端条件下当区间确实是包含全部时最后的结果会出错 第二种情况：ret = 一个很大的数（此题要取最优的最短区间）故 x 和 y 赋任何值都可以 （2）第三种情况：仅使用一个变量 x 记录区间的头，使用 x + ret - 1 来直接算出第二个值（最推荐这种方式可以避免很多边界情况）

2.2.3 代码

2.2.3.1 情况一

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N];
int n, m;
int kind; // 当前窗口不同画师量
int mp[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = 1;
    int ret = n; // 存储最短窗口
    int begin = 1;
    int end = n;
    while(r <= n){
        if(mp[a[r]]++ == 0) // 进窗口
            kind++;
        while(kind == m) // 判断
        {
            if(ret > r - l + 1) // 更新结果
            {
                ret = r - l + 1;
                begin = l;
                end = r;
            }
            if(mp[a[l++]]-- == 1) // 出窗口
                kind--;
        }
        r++;
    }
    cout << begin << " " << end << endl;
    return 0;
}

2.2.3.2 情况二

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N];
int n, m;
int kind; // 当前窗口不同画师量
int mp[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = 1;
    int ret = 1e7; // 存储最短窗口
    int begin = 1;
    int end = 1;
    while(r <= n){
        if(mp[a[r]]++ == 0) // 进窗口
            kind++;
        while(kind == m) // 判断
        {
            if(ret > r - l + 1) // 更新结果
            {
                ret = r - l + 1;
                begin = l;
                end = r;
            }
            if(mp[a[l++]]-- == 1) // 出窗口
                kind--;
        }
        r++;
    }
    cout << begin << " " << end << endl;
    return 0;
}

2.2.3.3 情况三

#include<iostream>
using namespace std;
const int N = 1e6+10;
int a[N];
int n, m;
int kind; // 当前窗口不同画师量
int mp[N];

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int l = 1, r = 1;
    int ret = n; // 存储最短窗口
    int begin = 1;
    while(r <= n){
        if(mp[a[r]]++ == 0) // 进窗口
            kind++;
        while(kind == m) // 判断
        {
            if(ret > r - l + 1) // 更新结果
            {
                ret = r - l + 1;
                begin = l;
            }
            if(mp[a[l++]]-- == 1) // 出窗口
                kind--;
        }
        r++;
    }
    cout << begin << " " << begin + ret - 1 << endl;
    return 0;
}

2.3 字符串

2.3.1 题目

链接：字符串

2.3.2 算法原理

定义一个变量 kind 记录当前窗口内统计到字符种类 （1）进窗口：right 位置元素记录到统计次数的哈希表中，如果次数是 0 变 1，说明窗口内多了「一种」字符，记录一下； （2）判断：当窗口内字符种类等于 m 时，窗口合法，right 停止右移（寻找到当前情况的最优解），接下来需要出窗口； （3）出窗口：让 left 所指位置的元素在哈希表中的次数减一，如果次数是 1 变 0，说明窗口内少了「一种」字符，记录一下； （4）更新结果：在判断成立时，窗口合法，此时更新窗口大小

2.3.3 代码

#include<iostream>
using namespace std;
string s;
int mp[350]; // 统计每个小写字符出现的次数
int kind; // 窗口的元素种类

int main(){
    cin >> s;
    int l = 0, r = 0;
    int ret = 1e7;
    while(r < s.size()){
        if(mp[s[r]]++ == 0) kind++;
        while(kind == 26){
            ret = min(ret, r - l + 1);
            if(mp[s[l++]]-- == 1) kind--;
        }
        r++;
    }
    cout << ret << endl;
    return 0;
}

2.4 丢手绢

2.4.1 题目

链接：丢手绢

2.4.2 算法原理

当我们「暴力枚举」的过程中，固定一个起点位置 left，然后 right 之后向后遍历时，记 [left,right] 之间的距离为 k。当 right 第一次扫描到 k × 2 > sum 时（以 left 为起点到的最远距离为 right - 1），此时我们会发现： • right 无需再向后遍历，因为继续向后走的结果一定不是最优的； • left 向后移动一格之后，right 指针也不用回退，因为我们已经维护出来一个合法区间的信息，right 回退也不是最优解。 解法： （1）进窗口：right 位置与前一个位置的距离累加到 k 中； （2）判断：k × 2 > sum 时，此时 right 指针不用前进，应该让 left 所指的元素出窗口 （3）出窗口：让 left 所指位置与前一个位置的距离累减到 k 中； （4）更新结果：需要在两个地方更新： a. 判断结束之后，此时 [left, right] 之间可能是最优解，用 k 更新结果； b. 判断成立的时候，此时 [right, left] 之间可能是最优解，用 sum − k 更新结果。

2.4.3 代码

#include<iostream>
using namespace std;
const int N = 1e5+10;
int a[N];

int main(){
    int n; cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i];
    }
    int l = 1, r = 1;
    int ret = 0;
    int k = 0;
    while(r <= n){
        k += a[r];
        while(2 * k > sum) // 用 sum - k 来更新结果
        {
            ret = max(ret, sum - k);
            k -= a[l++];
        }
        ret = max(ret, k); // 用 k 来更新结果
        r++;
    }
    cout << ret << endl;
    return 0;
}

总结

双指针算法通过优化暴力枚举策略，利用两个指针不回退的特性降低时间复杂度。本文讲解了滑动窗口在子区间统计中的应用，涵盖四个经典例题：寻找最长无重复字符子串（唯一的雪花）、最短包含所有类型元素的区间（逛画展）、特定字符种类统计（字符串）以及环形距离最值问题（丢手绢）。通过哈希表维护窗口状态，实现 O(n) 或 O(nlogn) 的时间复杂度优化，适合解决涉及连续子序列的统计与查找问题。