唯一的雪花

发表于 分类于 阅读次数： Waline： 本文字数： 196 阅读时长 ≈ 1 分钟

考点

  • 双指针
  • 滑动窗口

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 50;
unordered_map<int, int> vis;
int t, n, a[maxn];

void f() {
  vis.clear();
  int l = 1, r = 1, ans = 0;
  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  while (l <= r && r <= n) {
    while (r <= n && !vis[a[r]]) ++vis[a[r++]];
    ans = max(ans, r - l);
    while (a[l] != a[r]) --vis[a[l++]];
    --vis[a[l++]];
  }
  cout << ans << endl;
}

int main() {
  cin >> t;
  while (t--) f();
  return 0;
}

思路

用双指针维护一个滑动窗口：

  • 右指针所指的数字不重复，则向右扩展扩大窗口，同时用窗口大小更新答案；

  • 右指针所指的数字重复时，设该数为A，

    此刻窗口内有且只有一个A，那么将左指针向右扩展收缩窗口，直到窗口内无A停止收缩。