AcWing 799. 最长连续不重复子序列 C++ 双指针算法/map存位置
原题链接
简单
作者:
张立斌
,
2019-10-25 15:45:37
,
所有人可见
,
阅读 994
main函数
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
int main(void) {
int n;
scanf("%d", &n);
if (n < 0) {
puts("0");
return 0;
}
vector<int> numVec(n);
for (int i = 0; i < n; ++i) {
scanf("%d", &numVec[i]);
}
int res = lengthLongestSubArr(numVec);
printf("%d\n", res);
return 0;
}
双指针算法
int lengthLongestSubArr(const vector<int> &numVec) {
const int n = static_cast<int>(numVec.size());
int res = 0;
unordered_set<int> numSet(16);
int j = 0;
for (int i = 0; i < n; ++i) {
const int numI = numVec[i];
while (numSet.count(numI)) {
const int numJ = numVec[j];
numSet.erase(numJ);
++j;
}
numSet.insert(numI);
res = max(res, i - j + 1);
}
return res;
}
map存位置
int lengthLongestSubArr(const vector<int> &numVec) {
const int n = static_cast<int>(numVec.size());
int res = 0;
unordered_map<int, int> indexMap(16);
int j = 0;
for (int i = 0; i < n; ++i) {
const int numI = numVec[i];
j = max(j, indexMap[numI]);
indexMap[numI] = i + 1;
res = max(res, i - j + 1);
}
return res;
}