一、基础算法6：双指针算法模板题+算法模板（最长连续不重复子序列，数组元素的目标和，判断子序列）

不念不忘少年蓝@ 2023-10-09 17:59 1阅读 0赞

#### 文章目录 ####

*  算法模板
 *   *  双指针算法模板
     *  最长连续不重复子序列模板
     *   *  暴力法
         *  双指针算法
     *  数组元素的目标和模板
     *  判断子序列模板
 *  模板题
 *   *  最长连续不重复子序列
     *   *  原题链接
         *  题目
         *  题解
     *  数组元素的目标和
     *   *  原题链接
         *  题目
         *  题解
     *  判断子序列
     *   *  原题链接
         *  题目
         *  题解

## 算法模板 ##

### 双指针算法模板 ###

for (int i = 0, j = 0; i < n; i ++ )
    {
        
        while (j < i && check(i, j)) j ++ ;
    
        // 具体问题的逻辑
    }
    常见问题分类：
        (1) 对于一个序列，用两个指针维护一段区间
        (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

### 最长连续不重复子序列模板 ###

#### 暴力法 ####

//暴力法check函数
    int check(int l, int r)
    {
        
        for (int i = l+1; i <=r ; i++)
            for (int j = l; j < i; j++)
                if (a[i] == a[j])
                    return 1;
        return 0;
    } 
    //暴力法： 
    	for (int i = 0; i < n; i++)
    		for (int j = 0; j <= i; j++)
    			if (check(j, i) == 0)//检查 i 和 j 之间是否有重复的数字
    				res = max(res, i - j + 1);
    				
    	cout<<res;

#### 双指针算法 ####

//	双指针算法：
    	for(int i=1,j=1;i<=n;i++){
        
    		s[a[i]]++;
    		while(s[a[i]]>1){
         // 此时a[i]在序列中有重复值 
    			s[a[j]]--; //  在s中-- 维护s数组 
    			j++;// j++ j在左边找到第一个和a[i]重复的值 并维护j~i序列中没有重复的数 
    		}
    		res = max(res,i-j+1);
    		
    	} 
    	cout<<res;

### 数组元素的目标和模板 ###

int j=m-1;
    	for(int i=0;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;
    		}
    	}

### 判断子序列模板 ###

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";

## 模板题 ##

### 最长连续不重复子序列 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/801/][https_www.acwing.com_problem_content_801]

#### 题目 ####

799 . 最长连续不重复子序列  
给定一个长度为 n  
的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式  
第一行包含整数 n  
。

第二行包含 n  
个整数（均在 0∼105  
范围内），表示整数序列。

输出格式  
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围  
1≤n≤105  
输入样例：

5
    1 2 2 3 5

输出样例：

#### 题解 ####

![在这里插入图片描述][b510ef87f8bb427ebb101ed8387abbed.png]

#include <iostream>
    using namespace std;
    
    const int N = 1e5 + 10;
    int n;
    int a[N],s[N];
    
    暴力法check函数
    //int check(int l, int r)
    //{
        
    //    for (int i = l+1; i <=r ; i++)
    //        for (int j = l; j < i; j++)
    //            if (a[i] == a[j])
    //                return 1;
    //    return 0;
    //} 
    int main() {
        
    	cin>>n;
    	for(int i=1; i<=n; i++) cin>>a[i];
    
    	int res = 0;
    //	//暴力法： 
    //	for (int i = 0; i < n; i++)
    //		for (int j = 0; j <= i; j++)
    //			if (check(j, i) == 0)//检查 i 和 j 之间是否有重复的数字
    //				res = max(res, i - j + 1);
    //				
    //	cout<<res;
    
    //	双指针算法：
    	for(int i=1,j=1;i<=n;i++){
        
    		s[a[i]]++;
    		while(s[a[i]]>1){
         // 此时a[i]在序列中有重复值 
    			s[a[j]]--; //  在s中-- 维护s数组 
    			j++;// j++ j在左边找到第一个和a[i]重复的值 并维护j~i序列中没有重复的数 
    		}
    		res = max(res,i-j+1);
    		
    	} 
    	cout<<res;
    	return 0;
    }

### 数组元素的目标和 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/802/][https_www.acwing.com_problem_content_802]

#### 题目 ####

800 . 数组元素的目标和  
给定两个升序排序的有序数组 A  
和 B  
，以及一个目标值 x  
。

数组下标从 0  
开始。

请你求出满足 A\[i\]+B\[j\]=x  
的数对 (i,j)  
。

数据保证有唯一解。

输入格式  
第一行包含三个整数 n,m,x  
，分别表示 A  
的长度，B  
的长度以及目标值 x  
。

第二行包含 n  
个整数，表示数组 A  
。

第三行包含 m  
个整数，表示数组 B  
。

输出格式  
共一行，包含两个整数 i  
和 j  
。

数据范围  
数组长度不超过 105  
。  
同一数组内元素各不相同。  
1≤数组元素≤109  
输入样例：

4 5 6
    1 2 4 7
    3 4 6 8 9

输出样例：

1 1

#### 题解 ####

![在这里插入图片描述][98aa5f2b115d46e2afd413adc1ff62bc.png]  
![在这里插入图片描述][7e8d5f53ad6040948006d470def61578.png]

#include <iostream>
    using namespace std;
    const int N = 1e5 + 10;
    
    int a[N],b[N];
    int n,m,x;
    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]);
    	
    	int j=m-1;
    	for(int i=0;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;
    }

### 判断子序列 ###

#### 原题链接 ####

[https://www.acwing.com/problem/content/2818/][https_www.acwing.com_problem_content_2818]

#### 题目 ####

2816 . 判断子序列  
给定一个长度为 n  
的整数序列 a1,a2,…,an  
以及一个长度为 m  
的整数序列 b1,b2,…,bm  
。

请你判断 a  
序列是否为 b  
序列的子序列。

子序列指序列的一部分项按原有次序排列而得的序列，例如序列 \{a1,a3,a5\}  
是序列 \{a1,a2,a3,a4,a5\}  
的一个子序列。

输入格式  
第一行包含两个整数 n,m  
。

第二行包含 n  
个整数，表示 a1,a2,…,an  
。

第三行包含 m  
个整数，表示 b1,b2,…,bm  
。

输出格式  
如果 a  
序列是 b  
序列的子序列，输出一行 Yes。

否则，输出 No。

数据范围  
1≤n≤m≤105  
,  
−109≤ai,bi≤109  
输入样例：

3 5
    1 3 5
    1 2 3 4 5

输出样例：

Yes

#### 题解 ####

#include <iostream>
    using namespace std;
    const int N = 1e5 + 10;
    int a[N],b[N];
    int n,m;
    
    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) cout<<"Yes";
    	else cout<<"No";
    	return 0;
    }

[https_www.acwing.com_problem_content_801]: https://www.acwing.com/problem/content/801/
[b510ef87f8bb427ebb101ed8387abbed.png]: https://img-blog.csdnimg.cn/b510ef87f8bb427ebb101ed8387abbed.png
[https_www.acwing.com_problem_content_802]: https://www.acwing.com/problem/content/802/
[98aa5f2b115d46e2afd413adc1ff62bc.png]: https://img-blog.csdnimg.cn/98aa5f2b115d46e2afd413adc1ff62bc.png
[7e8d5f53ad6040948006d470def61578.png]: https://img-blog.csdnimg.cn/7e8d5f53ad6040948006d470def61578.png
[https_www.acwing.com_problem_content_2818]: https://www.acwing.com/problem/content/2818/