【算法|双指针系列No.9】AcWing 799. 最长连续不重复子序列 && AcWing 800. 数组元素的目标和 && AcWing 2816. 判断子序列-蒲公英云

【算法|双指针系列No.9】AcWing 799. 最长连续不重复子序列 && AcWing 800. 数组元素的目标和 && AcWing 2816. 判断子序列

小咪咪 2024-04-27 06:58 138阅读 0赞

个人主页：兜里有颗棉花糖
欢迎点赞? 收藏✨ 留言✉ 加关注?本文由兜里有颗棉花糖原创
收录于专栏【手撕算法系列专栏】
?本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
?希望我们一起努力、成长，共同进步。

一、AcWing 799. 最长连续不重复子序列

原题链接：点击直接跳转到该题目

解题代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int nums[N];
int b[N]; // 计数器
int main()
{
    int n,res = 0;
    cin >> n;
    for(int i = 0;i < n;i++) cin >> nums[i];
    for(int i = 0,j = 0;i < n;i++)
    {
        b[nums[i]]++;
        while(j < n && b[nums[i]] > 1) 
        {
            b[nums[j]]--;
            j++;
        }
        res = max(res,i - j + 1);
    }
    cout << res << endl;
    return 0;
}

二、AcWing 800. 数组元素的目标和

原题链接：点击直接跳转到该题目

解题代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N];
int main()
{
    int n,m,x;
    cin >> n >> m >> x;
    for(int i = 0;i < n;i++) cin >> a[i];
    for(int i = 0;i < m;i++) cin >> b[i];
    for(int i = 0,j = m - 1;i < n;i++)
    {
        while(j >= 0 && a[i] + b[j] > x) j--;
        if(a[i] + b[j] == x)
        {
            printf("%d %d\n",i,j);
            break;
        }
    }
    return 0;
}

三、AcWing 2816. 判断子序列

原题链接：点击直接跳转到该题目

解题代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N],b[N];
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < n;i++) cin >> a[i];
    for(int i = 0;i < m;i++) cin >> b[i];
    int i = 0,j = 0;
    while(i < n && j < m)
    {
        if(a[i] == b[j]) i++;
        j++;
    }
    if(i == n) cout << "Yes";
    else cout << "No";
    return 0;
}