题解 | #最长无重复子数组#

class Solution { public: /** * * @param arr int整型vector the array * @return int整型 */ int maxLength(vector& arr) { // write code here //首先这题要把每次访问的东西存到哈希表中去，因为可以利用哈希表查找所需时间很短的特点 //如果当前遇到的这个元素已经存在在哈希表中了，说明重复了，此时更新max，并把i直接跳到哈希表中value的位置的后一位（本来我只跳到了value位发现过不了，想了一下应该是跳到后一位） //而没有必要每次都只往后移动一位,这是一个很重要的优化点 //小白有一个很困惑的点，不知道这题双指针的点在哪？我这个代码应该是没用双指针才对,有知道的大佬 //欢迎回复我 int max=-1; unordered_map<int, int> hashMap;//定义一个哈希表，其中key表示数组元素的值，value表示在数组中的下标 int count=0;//记录每次最大的无重复个数 for(int i=0;i<arr.size();) { auto it=hashMap.find(arr[i]);//查找哈希表中是否有和arr[i]的值相等的键值 if(it==hashMap.end())//没找到 { count++;//计数器加1 hashMap[arr[i]]=i;//将该数组的值作为key值，下标作为value值 i++; } else{//如果在哈希表中找到了同样键值的元素 max=max>count?max:count;//更新max count=0; i=hashMap[arr[i]]+1;//将i跳过一部分无用的部分,关于这一个最重要的点，相信有一 //部分和我一样的小白没看懂，在最下面会有详细分析 hashMap.clear();//清空哈希表 } } max=max>count?max:count; return max; } }; /下面分析一下，i跳过一部分无用部分的原因，在我发现此时遇到的元素已经存在于哈希表中时，最容易想到的处理方式肯定是，更新max，然后清空哈希表把i往后移动一位，但是真的有必要移动一位吗？其实完全没必要。为什么？你可以想一下，如果我往后移动一位，到我上一次终止的地方为止，最好的情况就是我一个重复的都没遇到，此时最好情况下无重复个数还比上一次少1对吧，这还是最好情况下，如果中途就遇到一个重复的那小的肯定更多对吧，所以我只需要把i跳到上次终止位置时的下一个，直接从哈希表中就可得到。i跳过的部分一定不可能比我第一次的大，听懂打1（不是）。还不懂就画个数组看，使劲看/