本文最后更新于 718 天前,其中的信息可能已经有所发展或是发生改变。
Original Link
思想:
- 双指针。
- 快指针
i
作为某一连续最长不重复区间的右端点,慢指针 j
作为该区间的左端点;
- 遍历数组
a[i]
,用 vis[a[i]]
标记当前区间已经存在的数。
- 当
vis[a[i]] > 1
时:
- 说明当前区间存在重复数字,则
j
不断右移,期间 vis[a[j]] --
,直到 vis[a[i]] == 1
为止;
- 此时不含重复数字的区间长度即为
i - j + 1
,用 res
来维护最长的区间长度。
- 否则说明当前区间还未存在重复数字,
i
持续右移。
代码:
| #include <bits/stdc++.h> |
| using namespace std; |
| |
| const int N = 1e6 + 3; |
| |
| int a[N]; |
| |
| int vis[N]; |
| |
| void solve(){ |
| int n; cin >> n; |
| for(int i = 0; i < n; i ++) cin >> a[i]; |
| int res = 0; |
| for(int i = 0, j = 0; i < n; i ++){ |
| vis[a[i]] ++; |
| while(vis[a[i]] > 1 && j < i){ |
| vis[a[j]] --; |
| j ++; |
| } |
| res = max(res, i - j + 1); |
| } |
| cout << res << endl; |
| } |
| |
| int main(){ |
| solve(); |
| return 0; |
| } |