AcWing 799. 最长连续不重复子序列
原题链接
简单
作者:
uniqs
,
2024-01-09 18:07:56
,
所有人可见
,
阅读 44
最强性能篇
原理
- 在最差情况下,我们的i指针在前面跑,j指针在后面甩尾,j还是有一个不断的循环++的一个O(n)要跑,可以优化掉这个O(n)把O(2n)优化到O(n)
工程级应用版
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> d(n);
for (int& di : d) cin >> di;
unordered_map<int, int> n2idx;
int ret = 0;
for (int i = 0, start = 0; i < n; ++i) {
int di = d[i];
auto it = n2idx.find(di);
if (it != n2idx.end()) {
start = max(start, it->second + 1);
}
n2idx[di] = i;
ret = max(ret, i - start + 1);
}
cout << ret;
return 0;
}
适配性低一点但性能更高的【刷题版】(unordered_map并非真O(1),跑不过vector):
#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> d(n);
for (int& di : d) cin >> di;
vector<int> n2idx(100001);
int ret = 0;
for (int i = 0, start = 0; i < n; ++i) {
int di = d[i];
start = max(start, n2idx[di]);
n2idx[di] = i + 1;
ret = max(ret, i - start + 1);
}
cout << ret;
return 0;
}
$O(2n)=O(n)$ 啊
这就是刷题和工程级应用的区别,工程级应用能稳稳的的把2n优化到n的可以优化。刷题就无所谓了
### 视频讲解的版本(稍微工程级应用一点点)