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

题解一：暴力+hash表
主要思路:
①从1遍历到n，选取子数组的起点start
②第二重循环，从start下一个数字开始，选择子数组的结束位置end；
③直到end位置出现重复，记录最长的长度，跳转至步骤①，直到遍历完所有子数组的起点
图示：

复杂度分析:
时间复杂度：,双重循环分别找子数组的头部和尾部
空间复杂度:,最差情况下，整个数组都是不重复的。

实现如下:

class Solution {
public:
    /**
     *
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        int res=0;
        for(int i=0;i<arr.size();++i){//遍历选取子数组的起点
            unordered_set<int> se;
            se.insert(arr[i]);
            for(int j=i+1;j<arr.size();++j){//遍历找到子数组的尾部
                if(se.count(arr[j])){//已经出现重复了，结束本次循环
                    break;
                }else{//本数字没有出现重复
                    se.insert(arr[j]);
                }
            }
            res=max(res,(int)se.size());//判断该子数组是否为最长无重复子数组
        }
        return res;
    }
};

题解二：双指针+hash表
主要思路:
①两个指针start，end，指向数组开始的位置
②移动start指针，并将指向的数字与hash表中数字进行比较，不同则加入hash表，继续②操作
③当start指针指向的数字在hash表中出现重复时，移动end指针，并删除指向的数字，直到hash表中没有与start指向的数字重复时，跳转至②
④直到start遍历完数组。
⑤在每一次将start指向的数字加入hash时，统计hash表中的大小，最大的size就是本题目答案res。
图示：

复杂度分析:
时间复杂度：,左右指针都只会遍历一次数组
空间复杂度:,最差情况下，整个数组中的数字都是不重复的。

实现如下:

class Solution {
public:
    /**
     *
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        unordered_set<int> se;//存不重复的数字
        int i = 0, j = 0,res=0;
        while (i < arr.size()) {
            while (se.count(arr[i])) {//出现重复的数字，将hash表中这个值删除,删除到没有重复数字
                se.erase(arr[j++]);
            }
            se.insert(arr[i++]);//会将唯一的一个也删除，重新加入hash表中
            res = max(res, i - j);//统计此时的最大长度
        }
        return res;//返回结果
    }
};