文章详情

AcWing 2816. 判断子序列

作者：

linzy 浏览：98 2021年3月23日 01:47

### AcWing 2816. 判断子序列

#### 题目链接：

[AcWing 2816. 判断子序列](https://www.acwing.com/problem/content/description/2818/)

#### 解题思路：双指针

定义两个指针`i`、`j` 分别指向原序列和子序列，然后遍历原序列。

当`i`所指向的数与`j`所指向的数相等的时候说明原序列中已经有一个值与子序列配对，那么继续配对子序列的下一个数值。直到再次配对`j`才进行移动，否则就只有`i`在遍历。

当i遍历玩之后，判断`j`匹配的个数有多少个，如果`j`匹配的个数与答案相等，则说明该序列是原序列的子序列。

**双指针遍历过程：**

![AcWing 2816. 判断子序列](https://images.21hut.com/typora/202103/17/142011-1578.gif)

**证明双指针的正确性：**

双指针的性质：当一个指针移动的时候另一个指针不需要重复的遍历他已经遍历过的那些数来证明答案的正确性。从而达到两个指针只需要遍历一遍就可以解决问题。

分析题目：

![image-20210317143407312](https://images.21hut.com/typora/202103/17/143410-341680.png)

子序列的要求是按原有次序排列，所以要证明A序列是B序列的子序列。

要有两个条件：①A序列里面的数B序列里面都有②能找出一组跟A序列排序一样的序列，可以不连续，但相对位置一样

比如：

匹配到第一个数，要匹配第二个数的时候不能够匹配原来已经匹配过的数，尽管第二个数在之前已经出现过，而是要在匹配到的数后面进行寻找。因为`j`是往后移，所以第二个匹配的数，也要在第一个匹配的数后面进行寻找。

所以当`j`指针移动的时候`i`指针不能（不用）遍历他已经遍历过的数。

`i`移动的时候，j更不用重复遍历之前的数，因为之前的数已经匹配过了，没有这个需要。

#### 双指针代码：

```c++
#include<iostream>
using namespace std;
const int N = 1e5+10;
int str1[N],str2[N];

int main()
{
    int n,m;
    cin>>n>>m;
    
    for(int i = 0; i < n; i++ )cin>>str1[i];
    for(int i = 0; i < m; i++ )cin>>str2[i];
    
    int i = 0, j = 0;
    while(j < n && i < m)
    {
        //判断，如果匹配则i往前走，否则j继续匹配
        if(str1[j] == str2[i])j++,i++;
        else i++;
    }
    if( j == n)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}
```

AcWing 2816. 判断子序列

请登录后回复

共有0条评论