题解 | #最长无重复子数组#
1. 判断某个键是否存在时一定要用map.count(key)，而不要用map[key]避免该值本身是0的情况
2. 不能不消除上一个子序列在map中的键值，否则就会在后续某个值和前面某序列有重复值时left指针跳到前面
3. 注意尾部处理，假如最后一个值不与窗口内的重复的话就会跳过count的计算
class Solution {
public:
/**
*
* @param arr int整型vector the array
* @return int整型
*/
int maxLength(vector<int>& s) {
if(s.size() == 1) return 1;
unordered_map <int, int> map; //键：记录数字， 值：记录该数字所在的位置
int maxcount = 0;
int left = 0, right = 0;
while(right < s.size()){
if(!map.count(s[right])){
map[s[right]] = right;
right++;
}else{
int count = right - left;
if(count > maxcount) maxcount = count;
left = map[s[right]]+1;
map.clear();
right = left;
}
}
int count = right - left;
if(count > maxcount) maxcount = count;
return maxcount;
}
}; 但是这种方法存在重复遍历的情况，效率比较低 为了解决指针不跳转至中间的情况，我们再对哈希表中重复出现的情况做一个判断：是否在窗口内
采用滑动窗口的解法：
if(s.size() == 1) return 1;
unordered_map <int, int> map; //键：记录数字， 值：记录该数字所在的位置
int maxcount = 0;
int left = 0, right = 0;
while(right < s.size()){
if(!map.count(s[right])||map[s[right]] < left){
map[s[right]] = right;
}else {
int count = right - left;
if(count > maxcount) maxcount = count;
left = map[s[right]]+1;
map[s[right]] = right;
}
right ++;
}
int count = right - left;
if(count > maxcount) maxcount = count;
return maxcount; 
CVTE公司福利 265人发布
投递牛客等公司10个岗位 >
查看5道真题和解析