题目描述
STL 哈希表版
样例
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n = 0;
cin >> n;
vector<int> arr;
for (int i = 0; i < n; i ++) {
int num = 0;
scanf("%d", &num);
arr.push_back(num);
}
// 双指针 我们枚举结尾位置 即右指针代表结尾
// 假定[l, r]为合法区间 则r右移的时候 l应该一直右移到不出现重复数字(!=arr[r])为止
int l = 0, r = 0;
unordered_map<int, int> cnt; // key: num value: 次数
int result = 0;
while (r < n) {
auto it = cnt.find(arr[r]);
cnt[arr[r]] ++;
while (cnt[arr[r]] > 1) {
cnt[arr[l]] --;
l ++;
}
result = max(result, r - l + 1);
r ++;
}
cout << result << "\n";
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla