判断子序列

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int n, m;
int a[N], b[N];
bool flag;
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++ i) cin >> a[i];
    for (int j = 0; j < m; ++ j) cin >> b[j];
    // 利用for循环遍历两个数组
    // 思路就是看一下这个遍历b数组的时候 这个a数组是否会走完
    // 如果这个a数组走完了 那么就代表的是 
    // 这个长度更小的a数组是b数组的子序列
    for (int i = 0, j = 0; i < m && j < n; ++ i) 
    {
        // 首先判断的是 两个数组的元素是否相等 如果想的的话
        // 这个a数组就往后走一格
        if (b[i] == a[j]) j ++;
        // 当走完的时候 设置flag=true
        if (j == n) flag = true;
    }
    if (flag) cout << "Yes";
    else cout << "No";
    return 0;
}

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int [] a = new int [n + 10];
        int [] b = new int [m + 10];
        for (int i = 0; i < n; ++ i) a[i] = in.nextInt();
        for (int j = 0; j < m; ++ j) b[j] = in.nextInt();
        boolean flag = false;
        int j = 0;
        for (int i = 0; i < m; ++ i)
        {
            if (a[j] == b[i]) j ++;
            if (j == n)
            {
                flag = true;
                break;
            }
        }
        if (flag) System.out.println("Yes");
        else System.out.println("No");
    }
}

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;

int a[N], s[N];
int n, res;

int main()
{
    cin >> n;
    for (int i = 0; i < n; ++ i) cin >> a[i];
    for (int i = 0, j = 0; i < n; ++ i)
    {
        s[a[i]] ++; // 记录下a[i]出现的次数
        while(s[a[i]] > 1)   // 一点碰见两个重复的元素后
        {  
            s[a[j]] --;  // 这里要主要的一点是这个算法是没有回溯的
                         // 不要被for循环里面的条件误导以为会回溯、
                         // 现在遇到两个相同的元素了
                         // ！！！ 现在是这个算法最厉害的地方 
                         // 这个j代表的是 j可以到达最左的地方 所以在j左边的
                         // 元素的个数就需要都-- 这点很妙
                         // 每次求的是 j到i之间的符合条件的最大值
            j ++;        // 然后j++
        }
        res = max(res, i - j + 1);  // 这个res的含义是 在i这个位置、
        // 可以达到的符合题目条件的最大长度
    }
    cout << res;
    return 0;
}

import java.io.*;
import java.util.*;

public class Main
{
    public static void main(String[] args) throws IOException{
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int [] a = new int [n + 10];
        int [] s = new int [n + 10];
        int res = 0;
        for (int i = 0; i < n; ++ i) a[i] = in.nextInt();
        for (int i = 0, j = 0; i < n; ++ i)
        {
            s[a[i]] ++;
            while(s[a[i]] > 1)
            {
                s[a[j]] --;
                j ++;
            }
            res = Math.max(res, i - j + 1);
        }
        System.out.println(res);
    }
}