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

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

在这里插入图片描述

一、双指针

双指针算法有时候也叫尺取法或者滑动窗口，是一种优化暴力枚举策略的手段： • 当我们发现在两层 for 循环的暴力枚举过程中，两个指针是可以不回退的，此时我们就可以利用两个指针不回退的性质来优化时间复杂度。 • 因为双指针算法中，两个指针是朝着同一个方向移动的，因此也叫做同向双指针。注意：希望大家在学习该算法的时候，不要只是去记忆模板，一定要学会如何从暴力解法优化成双指针算法。不然往后遇到类似题目，你可能压根都想不到用双指针去解决。

二、双指针经典算法题

2.1 唯一的雪花

2.1.1 题目

链接：唯一的雪花

在这里插入图片描述

2.1.2 算法原理

我们「暴力枚举」的过程中，固定一个起点位置 left，然后之后 right 向后遍历时。当 right 第一次扫描到一个位置，使 [left,right] 这个区间「出现重复字符」，此时我们会发现： • right 无需再向后遍历，因为继续向后走区间窗口也是「不合法」的； • left 向后移动一格之后，right 指针也不用回退，因为我们已经维护出来 [left,right] 区间的信息，并且以 left + 1 为起点的最优解一定不会比 left 为起点的好 当我们发现暴力枚举的「两个指针不回退」时，就可以用「滑动窗口」优化：（1）进窗口：right 位置元素记录到统计次数的哈希表中；（2）判断：当哈希表中 right 位置的值出现超过 1 次之后，窗口内子串不合法；（3）出窗口：让 left 所指位置的元素在哈希表中的次数减一；（4）更新结果：判断结束之后，窗口合法，此时更新窗口的大小。 技巧：（1）哈希表可以使用 STL 或者使用数组模拟一个哈希效果（2）依照题意可能在判断条件内也可能在判断条件外

2.1.3 代码

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

int main(){
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        for(int i = 1; i <= n; i++) cin >> a[i];
        int l = 1, r = 1;
        unordered_map<int,int> mp; // 维护窗口内所有元素出现的次数
        int ret = 1;
        while(r <= n){
            mp[a[r]]++; // 进窗口
            while(mp[a[r]] > 1) // 判断---窗口不合法的情况
                mp[a[l++]]--;
            ret = max(ret, r - l + 1); // 更新结果
            r++;
        }
        cout << ret << endl;
    }
    return 0;
}

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) 的时间复杂度优化，适合解决涉及连续子序列的统计与查找问题。

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

一、双指针

二、双指针经典算法题

2.1 唯一的雪花

2.1.1 题目

2.1.2 算法原理

2.1.3 代码

2.2 逛画展

2.2.1 题目

2.2.2 算法原理

2.2.3 代码

2.2.3.1 情况一

2.2.3.2 情况二

2.2.3.3 情况三

2.3 字符串

2.3.1 题目

2.3.2 算法原理

2.3.3 代码

2.4 丢手绢

2.4.1 题目

2.4.2 算法原理

2.4.3 代码

总结

更多推荐文章

相关免费在线工具

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

一、双指针

二、双指针经典算法题

2.1 唯一的雪花

2.1.1 题目

2.1.2 算法原理

2.1.3 代码

2.2 逛画展

2.2.1 题目

2.2.2 算法原理

2.2.3 代码

2.2.3.1 情况一

2.2.3.2 情况二

2.2.3.3 情况三

2.3 字符串

2.3.1 题目

2.3.2 算法原理

2.3.3 代码

2.4 丢手绢

2.4.1 题目

2.4.2 算法原理

2.4.3 代码

总结

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具