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

题目主要信息:

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

举一反三：

学习完本题的思路你可以解决如下题目：

BM90. 最小覆盖子串

方法：滑动窗口(推荐使用)

知识点1：滑动窗口

滑动窗口是指在数组、字符串、链表等线性结构上的一段，类似一个窗口，而这个窗口可以依次在上述线性结构上从头到尾滑动，且窗口的首尾可以收缩。我们在处理滑动窗口的时候，常用双指针来解决，左指针维护窗口左界，右指针维护窗口右界，二者同方向不同速率移动维持窗口。

知识点2：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

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

而保证窗口内的元素不重复，我们可以使用根据key值快速访问的哈希表，key值为窗口内的元素，value为其出现次数，只要新加入窗口的元素出现次数不为1，就是重复。

while(mp.get(arr[right]) > 1) 
    //窗口左移，同时减去该数字的出现次数
    mp.put(arr[left],mp.get(arr[left++])-1); 

具体做法:

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

图示：

Java代码实现:

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

C++代码实现:

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]]++; 
            //出现次数大于1，则窗口内有重复
            while(mp[arr[right]] > 1) 
                //窗口左移，同时减去该数字的出现次数
                mp[arr[left++]]--; 
            //维护子数组长度最大值
            res = max(res, right - left + 1); 
        }
        return res;
    }
};

Python实现代码：

class Solution:
    def maxLength(self , arr: List[int]) -> int:
        #哈希表记录窗口内非重复的数字
        mp = dict() 
        res = 0
        left = 0
        #设置窗口左右边界
        for right in range(len(arr)): 
            if arr[right] in mp:
                #窗口右移进入哈希表统计出现次数
                mp[arr[right]] += 1 
            else:
                mp[arr[right]] = 1
            #出现次数大于1，则窗口内有重复
            while mp[arr[right]] > 1: 
                #窗口左移，同时减去该数字的出现次数
                mp[arr[left]] -=1 
                left += 1
            #维护子数组长度最大值
            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$