最长连续不重复子序列

题目描述

给定一个长度为 $n(1\le n\le {10}^5)$ 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

样例输入

5
1 2 2 3 5

样例输出

3

题目分析

设 $i$ 指针指向合法区间的左端点，$j$ 指针指向合法区间的右端点，$s$ 数组记录当前区间内每个数的出现次数。

1. 遍历 $j$ 指针，对于每个 $a[j]$，$s[a[j]]$ 加 1，表示当前数出现了一次。
2. 如果 $s[a[j]]>1$，说明当前数之前出现过，需要移动 $i$ 指针，直到 $s[a[j]]$ 减到 $1$ 为止。
3. 更新答案 $res=max(res,j-i+1)$。

示例代码

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

const int N = 1e5 + 10;
int a[N], s[N];


int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int res = 0;
    for (int i =0, j = 0; j < n; j++) {
        s[a[j]] ++;
        while (s[a[j]] > 1) {
            s[a[i]]--;
            i++;
        }

        res = max(res, j - i + 1);
    }
    cout << res << endl;

    return 0;
}

数组元素的目标和

题目描述

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

数组下标从 $0$ 开始。

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

数据保证有唯一解。

输入格式

第一行包含三个整数 $n,m,x$。

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

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

输出格式

一行，满足条件的数对 $(i,j)$。

样例输入

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

样例输出

1 1

题目分析

考虑到数组 $A$ 和 $B$ 都是升序排序的，因此可以用双指针的方法来解决。

设 $i$ 指针指向 $A$ 数组的左端点，$j$ 指针指向 $B$ 数组的右端点，考虑 $i$ 指针向右移动的过程中，如果 $A[i]+B[j]>x$，则 $j$ 指针不停向左移动，直到 $A[i]+B[j]\le x$。此时判断 $A[i]+B[j]=x$ 是否成立，如果成立，输出 $(i,j)$ 并退出循环。

示例代码

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

int n, m, x, a[100010], b[100010];

int main() {
    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) {
            cout << i << " " << j << endl;
            break;
        }
    }

    return 0;
}

判断子序列

题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots ,a_n$，以及一个长度为 $m$ 的整数序列 $b_1,b_2,\cdots ,b_m$。

请你判断 $a_1,a_2,\cdots ,a_n$ 是否为 $b_1,b_2,\cdots ,b_m$ 的子序列。

子序列指序列的一部分项按原有次序排列而得的序列，例如序列 $a_1,a_3,a_5$ 是序列 $a_1,a_2,a_3,a_4,a_5$ 的一个子序列。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数，表示整数序列 $a_1,a_2,\cdots ,a_n$。

第三行包含 $m$ 个整数，表示整数序列 $b_1,b_2,\cdots ,b_m$。

输出格式

一行，如果 $a_1,a_2,\cdots ,a_n$ 是 $b_1,b_2,\cdots ,b_m$ 的子序列，输出 "Yes"；否则输出 "No"。

样例输入

3 5
1 3 5
1 2 3 4 5

样例输出

Yes

题目分析

考虑枚举 $a$ 中的每一个元素在 $b$ 中是否存在，如果存在则 $i$ 指针加一，而不论是否存在，$j$ 指针都加一。这种做法是正确的，证明略。

示例代码

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

const int N = 1e5 + 10;
int n, m, a[N], b[N];

int main() {
    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) puts("Yes");
    else puts("No");

    return 0;
}