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

2.2 逛画展

题目链接：洛谷 P1638

思路分析

本题要求包含所有 m 种画师的最短区间。核心在于统计窗口内不同画师的数量 kind。

• 当 kind == m 时，窗口合法，尝试收缩左边界以寻找更优解；
• 若某画师数量减为 0，则 kind 减一，窗口再次变为不合法。

关于边界处理，推荐使用一个变量记录最短长度，结合起始点计算结束点，避免初始化带来的歧义。

代码实现

#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 字符串

题目链接：牛客网 18386

思路分析

此题是上一题的变种，要求包含所有小写字母（共 26 种）。逻辑完全一致，只是统计对象变成了字符集。使用定长数组 mp[350] 即可覆盖 ASCII 码范围。

代码实现

#include <iostream>
#include <string>
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 丢手绢

题目链接：牛客网 207040

思路分析

这是一个环形结构的问题。设总距离为 sum，当前窗口距离和为 k。当 2 * k > sum 时，说明当前区间已经超过了半圈，继续扩大只会让另一侧更短。此时应收缩左边界。

更新结果时有两处关键点：

1. 判断结束后，[left, right] 可能是最优解，用 k 更新；
2. 判断成立时，[right, left]（即剩余部分）可能是最优解，用 sum - k 更新。

代码实现

#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) { // 判断
            ret = max(ret, sum - k); // 用 sum - k 来更新结果
            k -= a[l++];             // 出窗口
        }
        ret = max(ret, k); // 用 k 来更新结果
        r++;
    }
    cout << ret << endl;
    return 0;
}

以上四个题目涵盖了双指针在不同场景下的应用。掌握从暴力枚举到滑动窗口的思维转变，是解决此类问题的关键。在实际编码中，务必注意边界条件的判断以及数据类型的溢出风险。