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

题目主要信息:

题目给定一个数组，要找到其中最长的无重复的子数组的长度
子数组必须是数组中连续的一段

具体思路:

既然要找一段连续子数组的内不重复的长度，我们可以使用滑动窗口，窗口内都是不重复的，然后窗口右界不断向右滑，如果窗口内出现了重复数组，说明新加入的元素与之前的重复了，只需要窗口左界也向右收缩就可以保证窗口内都是不重复的。

step 1：使用unordered_map构建一个哈希表，用于统计数组元素出现的次数。
step 2：窗口左右界都从数组首部开始，每次窗口优先右移右界，并统计进入窗口的元素的出现频率。
step 3：一旦右界元素出现频率大于1，就需要右移左界直到窗口内不再重复，将左边的元素移除窗口的时候同时需要将它在哈希表中的频率减1，保证哈希表中的频率都是窗口内的频率。
step 4：每轮循环，维护窗口长度最大值。

具体过程可以参考如下图示： alt

代码实现:

class Solution {
public:
    int maxLength(vector<int>& arr) {
        unordered_map<int, int> mp; //哈希表记录窗口内非重复的数字
        int res = 0;
        for(int left = 0, right = 0; right < arr.size(); right++){ //设置窗口左右边界
            mp[arr[right]]++; //窗口右移进入哈希表统计出现次数
            while(mp[arr[right]] > 1) //出现次数大于1，则窗口内有重复
                mp[arr[left++]]--; //窗口左移，同时减去该数字的出现次数
            res = max(res, right - left + 1); //维护子数组长度最大值
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，外循环窗口右界从数组首右移到数组尾，内循环窗口左界同样如此，因此复杂度为 $O (n + n) = O (n)$
空间复杂度： $O (n)$ ，最坏情况下整个数组都是不重复的，哈希表长度就为数组长度 $n$