two point（双指针）

 
#include 
#include 
#include 
 
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
        cin >> a[i];
    for(int j=0;j
        cin >> b[j];
    
    int i=0,j=m-1;
    
/**
     * 如果a[i]+b[j]>x,那么一定有a[i+1]+b[j]>x; 所以--j;
     * 如果a[i]+b[j]
*/
 
    for(i,j;i=0;)
    {
        if(a[i]+b[j]==x)
            break;
        else if(a[i]+b[j]>x) 
            --j;
        else 
            ++i;
    }
    
    cout << i << ' ' << j << endl;
    return 0;
}

解法二：

 
#include 
#include 
#include 
 
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
        cin >> a[i];
    for(int j=0;j
        cin >> b[j];
    
    int i=0,j=m-1;
    for(i,j;i=0;++i)
    {
        while(j>=0&&a[i]+b[j]>x) //显然，a[i]+b[j]>x,一定有a[i+1]+b[j]>x
            --j;
        if(j>=0&&a[i]+b[j]==x)
            cout << i << ' ' << j << endl;
    }
    
    return 0;
}

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 
#include 
#include 
 
using namespace std;
 
int main()
{
    int n,m;
    cin >> n >> m;
    int a[n],b[m];
    for(int i=0;i
        cin >> a[i];
    for(int i=0;i
        cin >> b[i];
    
    int i=0,j=0;
    while(i
    {
        if(a[i]==b[j])  ++i;
        ++j;
    }
    
    if(i==n)
        cout << "Yes\n";
    else 
        cout << "No\n";
    return 0;
}