【AcWing】双指针算法

🎆音乐分享 

Here With You – Asher Monroe
 

---

这一篇博客也用了双指针算法，同学们可以参考一下

代码随想录算法训练营第一天 | 题目2（LeetCode27移除元素）_小吉.cpp的博客-CSDN博客

老实说，双指针算法，顾名思义，就是两个指针，其实是一种优化方式 

下面的题目大家看代码和注释就能理解了 

🚥🚥🚥 

799. 最长连续不重复子序列 – AcWing题库

蓝色的箭头是 i

红色的箭头是 j 

代码

#include <iostream>
using namespace std;

const int N = 100010;
int a[N], count[N];
int n, ans;

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    for (int i = 0, j = 0; j < n; j++) {
        count[a[j]] ++;
        while (count[a[j]] > 1) {  //注意是>1,不是>=1 当count=1时，不会--
            count[a[i]] --;
            i++;
        }
        ans = max(ans, j - i + 1);
    }
    printf("%d", ans);
    return 0;
}

800. 数组元素的目标和 – AcWing题库

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m, x;
int a[N], b[N];

int main()
{
    scanf("%d%d%d", &n, &m, &x);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);

    for (int i = 0, j = m - 1; i < n; i ++ )  //j=m-1
    {
        while (j >= 0 && a[i] + b[j] > x) j -- ;                        //移动j指针
        if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;  //移动i指针
    }

    return 0;
}

2816. 判断子序列 – AcWing题库

 这个while循环使用的特别妙

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;
int a[N], b[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);

    int i = 0, j = 0;
    while (i < n && j < m)
    {
        if (a[i] == b[j]) i ++ ;//匹配上
        j ++ ;                  //没有匹配上
    }

    if (i == n) puts("Yes");
    else puts("No");

    return 0;
}

 1238. 日志统计 – AcWing题库

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

int n, d, k, cnt[N]; //用于存储每个id号获得赞数，所以后面代码为cnt[t] ++
PII logs[N];
bool st[N];  // 记录每个帖子是否是热帖

int main()
{
    scanf("%d%d%d", &n, &d, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d%d", &logs[i].first, &logs[i].second);

    sort(logs, logs + n);

    for (int i = 0, j = 0; i < n; i ++ )
    {
        int id = logs[i].second;//加入新的帖子
        cnt[id] ++ ;//获得一个赞

        while (logs[i].first - logs[j].first >= d)//两个帖子的时间跨度如果>=d,那么这个赞无效
        {
            cnt[logs[j].second] -- ;//删除这个id
            j ++ ;//指针移动
        }

        if (cnt[id] >= k) st[id] = true;//当前id是否>=k,如果>=k,那么就是热帖
    }

    for (int i = 0; i <= 100000; i ++ )
        if (st[i])
            printf("%d\n", i);

    return 0;
}

1031-组队_牛客竞赛语法入门班数组模拟、枚举、贪心习题 (nowcoder.com)

在下面的代码中，有一步while(r<=n&&a[r]-a[l]<=k) r++;

为什么会一直r++,并且r不会每次都变为0

其实就是因为已经是排好顺序的，

+a[l]是小于a[r]的，每次l++,大的数满足<=k,小的数一定满足<=k

#include <iostream>
#include <algorithm>

using namespace std;

int a[200005],b[200005];
int main()
{
    int t;
    cin>>t;
    int n,k;
    while(t--){
        cin>>n>>k;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n);
        int l=1,r=1;
        int res=0;
        for(;l<=n;l++){
            while(r<=n&&a[r]-a[l]<=k) r++;
            res=max(res,r-l);
        }
        cout<<res<<endl;
    }
}

下面这道题有点迷惑人，有意思

1027-字符串_2021秋季算法入门班第一章习题：模拟、枚举、贪心 (nowcoder.com) 

 小N现在有一个字符串S。他把这这个字符串的所有子串都挑了出来。

一个S的子串T是合法的，当且仅当T中包含了所有的小写字母。（就是26个字母）

小N希望知道所有的合法的S的子串中，长度最短是多少。

// 尺取法
#include<iostream>
#include<string>

using namespace std;
int a[27] = {0};

int main(){
    string s;
    cin >> s;
    int len = s.length();
    int minLength = len+1, c=0;
    for(int i=0, j=0; i<len; i++){
        if(a[s[i] - 'a'] == 0){//字母
            c++;
        }
        a[s[i] - 'a']++;
        while(a[s[j] - 'a'] > 1){
            a[s[j] - 'a']--;
            j++;
        }
        if(c == 26){
            minLength = min(minLength, i-j+1);
        }
    }


    cout<<minLength<<endl;

    return 0;
}

Code over!