01_最长连续不重复子序列 longest_continuous_non-repeating_subsequence

朴素算法: O(n^2)

for (i = 0; i < n; i++)
    for (j = 0; j <= i; j++)
        if (check(i, j) {
            // 每道题的具体逻辑
        }

双指针算法: O(n)

**核心思想: 先想暴力 -> 优化（找单调性，降低一个维度）**

for (i = 0; j = 0; i < n; i++) {
    while (j < i && check(i, j)) j++;
    // 每道题的具体逻辑
}

#include <iostream>

using namespace std;

const int N = 100010;
int n, a[N], f[N], res;

int main() {
    scanf("%d", &n);

    /* 
    i, j 都单调，
    i: 探索区间最右边界
    */
    for (int i = 0, j = 0; i < n; i++) {
        scanf("%d", &a[i]);
        f[a[i]]++; // 统计出现频率

        /* 
        不用判断 j <= i : 因为是遇到重复的数就马上减，保证了区间 [j, i] 最多只有一个重复的数，
        而 i 指的就是那个重复的数，所以在把重复的数的频率减到 1 之前 j 肯定 <= i（j 最多和 i 重合）
        例: (1)   9 6 5 4 9
            减完:   j     i （j < i）
            (2)   1 2 3 4 4
            减完:         ji（j = i）
        */
        while (f[a[i]] > 1) {
            /*
            因为后面的区间不能包含前面重复的数，所以前面的数的出现频率都需要减 1，
            即把重复的左数（1231, 第一个 1 就是重复的左数）及其之前的数的频率都减 1，
            j 边向后移动边减频率，直到 [j, i] 区间无重复的数
            */
            f[a[j]]--;
            j++;
        }

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

    printf("%d\n", res);

    return 0;
}

02_数组元素的目标和 arr_target_sum

#include <iostream>

using namespace std;

const int N = 100010;
int n, m, x;
int a[N], b[N];

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]);

    // O(n + m)
    // 不用判断 i < n && j >= 0: 因为有且有唯一解
    for (int i = 0, j = m - 1; ; i++) {
        while (a[i] + b[j] > x) j--; // 单调性: i 往后走递增，j 一定往前走递减
        if (a[i] + b[j] == x) {                 
            printf("%d %d\n", i, j);
            break;
        }
    }

    return 0;
}

03_判断子序列 judge_subsequence

#include <iostream>

using namespace std;

const int N = 100010;
int n, m;
int a[N], b[N];

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;
    for (int j = 0; j < m && i < n; j++) {
        if (b[j] == a[i]) i++; // 按顺序找，找到一个再找下一个
    }

    if (i == n) printf("Yes\n");
    else printf("No\n");

    return 0;
}