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

2.2 逛画展

2.2.1 题目

链接：逛画展

2.2.2 算法原理

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

关于答案输出的多种处理方式，这里分享一些踩坑经验：

• 初始化问题：如果用两个变量 x 和 y 记录左右下标，初始化会影响结果。例如 ret = n 时，极端条件下当区间确实包含全部时最后的结果会出错。
• 推荐方式：仅使用一个变量 x 记录区间的头，使用 x + ret - 1 来直接算出第二个值。这种方式可以避免很多边界情况。

2.2.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;
    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;
}

方案二：大数初始化

#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;
}

方案三：计算推导（推荐）

#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. 更新结果：需要在两个地方更新：
   • 判断结束之后，此时 [left, right] 之间可能是最优解，用 k 更新结果；
   • 判断成立的时候，此时 [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;
}