NC41 最长无重复子数组
题目描述
给定一个数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
示例1
输入：
[2,3,4,5]
返回值：
4
说明：
[2,3,4,5]是最长子数组
示例2
输入：
[2,2,3,4,3]
返回值：
3
说明：
[2,3,4]是最长子数组
示例3
输入：
[9]
返回值：
1
示例4
输入：
[1,2,3,1,2,3,2,2]
返回值：
3
说明：
最长子数组为[1,2,3]
示例5
输入：
[2,2,3,4,8,99,3]
返回值：
5
说明：
最长子数组为[2,3,4,8,99]
备注：
\(1 \leq n \leq 10^5\)
解题思路
滑动窗口 + 哈希判重。
第一种实现是利用队列，好写好理解，缺点是浪费内存；
第二种是利用两个指针记录窗口的开始结束位置，并不真的保存元素（没必要）；
这里题目只告诉了数组大小10的5次方，没有给出元素取值范围，否则还可以用 bitmap 代替 hashset，进一步减少内存占用。
参考代码
队列
class Solution {
public:
/**
*
* @param arr int整型vector the array
* @return int整型
*/
int maxLength(vector<int>& arr) {
// write code here
size_t res = 0;
deque<int> dq;
unordered_set<int> vis;
for (int x : arr) {
if (!vis.count(x)) {
dq.push_back(x);
vis.insert(x);
} else {
res = max(res, dq.size());
int fr;
do {
fr = dq.front();
dq.pop_front();
vis.erase(fr);
} while (fr != x);
dq.push_back(x);
vis.insert(x);
}
}
res = max(res, dq.size());
return res;
}
};
双指针
class Solution {
public:
/**
*
* @param arr int整型vector the array
* @return int整型
*/
int maxLength(vector<int>& arr) {
// write code here
int res = 0;
int left = 0, right = 0;
unordered_set<int> vis;
for (int x : arr) {
if (!vis.count(x)) {
right++;
vis.insert(x);
} else {
res = max(res, right - left);
int fr;
do {
fr = arr[left];
left++;
vis.erase(fr);
} while (fr != x);
right++;
vis.insert(x);
}
}
res = max(res, right - left);
return res;
}
};