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

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

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

#### 目录 ####

*  一、AcWing 799. 最长连续不重复子序列
 *   *  解题代码
 *  二、AcWing 800. 数组元素的目标和
 *   *  解题代码
 *  三、AcWing 2816. 判断子序列
 *   *  解题代码

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

**原题链接：[点击直接跳转到该题目][Link 3]**

### 解题代码 ###

#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. 数组元素的目标和 ##

**原题链接：[点击直接跳转到该题目][Link 4]**

### 解题代码 ###

#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. 判断子序列 ##

**原题链接：[点击直接跳转到该题目][Link 5]**

### 解题代码 ###

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

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[Link 2]: https://blog.csdn.net/m0_74352571/category_12364106.html
[7d5f5c0522df4548bdccccb6842f0211.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/0aae0e9116f44b438702ea10b5b0b02e.png
[Link 3]: https://www.acwing.com/problem/content/801/
[Link 4]: https://www.acwing.com/problem/content/802/
[Link 5]: https://www.acwing.com/problem/content/2818/