AcWing 799. 最长连续不重复子序列

原题链接：https://www.acwing.com/problem/content/description/801/

思路：

• 用一个pos[]数组来存储某个数上次出现的位置

• 双指针i和j，表示当前最长不重复区间[i,j)。每当将要把nums[j]纳入区间时，考察nums[j]上次出现的位置。
  • 若在i的左侧，则可以直接把nums[j]纳入最长不重复区间。
  • 否则，将i移动到nums[j]上次出现位置的右侧。

#include <iostream>
#include <cstring>

#define N 100005

int nums[N];

// 记录一个数上次出现的位置
int pos[N];

int n;

// 区间[i, j)，j表示下一个将要纳入区间的数的下标
int longest_repeat() {
    int i = 0, j = 1, max = 0;
    while (j <= n) {
        if (j - i > max) max = j -i;
        if (j == n) break;
        if (nums[i] == nums[j]) j++;
        else i = j++;
    }
    return max;
}

// 区间[i, j)，j表示下一个将要纳入区间的数的下标
int longest_non_repeat() {
    int i = 0, j = 0, max = 0;
    while (j <= n) {
        if (j - i > max) max = j - i;
        if (j == n) break;
        int cur = nums[j];
        // 如果当前的数cur出现过，则将i移动到cur上次出现的位置的右侧
        if (pos[cur] >= i) i = pos[cur] + 1;
        pos[cur] = j++;
    }
    return max;
}


int main() {
    memset(pos, -1, sizeof pos);
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &nums[i]);
    printf("%d", longest_non_repeat());
    return 0;
}