题目主要信息:

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

具体思路:

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

  • 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),外循环窗口右界从数组首右移到数组尾,内循环窗口左界同样如此,因此复杂度为O(n+n)=O(n)O(n+n)=O(n)
  • 空间复杂度:O(n)O(n),最坏情况下整个数组都是不重复的,哈希表长度就为数组长度nn