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

思路

1、哈希map，存放元素-索引
2、一个指针表示最长无重复区间的开始，一个指针代表最长无重复区间的结束；当遇到不同元素时，将其加入到map中，第二个指针++，获取长度；当遇到重复的元素时，更新长度，更新i指针为之前重复元素的索引+1，重置map，j=i+1

代码

class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    /*
    int maxLength(vector<int>& arr) {
        // write code here
        int i = 0;
        int len = arr.size();
        int res = 0;
        unordered_set<int> my_set;
        int tmp = 0;
        while(i<len){

            while(i<len && my_set.find(arr[i])==my_set.end()){
                my_set.emplace(arr[i]);
                tmp++;
                i++;

            }
            res = max(res, tmp);
            if(i==len){
                return res;
            }

            my_set.clear();
            my_set.emplace(arr[i]);
            tmp=1;
            i++;
        }

        return res;
    }
    */

    int maxLength(vector<int>& arr) {
        int i = 0;
        int j = 1;
        int res = 1;
        unordered_map<int, int> _map;            // 存放（值，索引）
        _map[arr[i]] = i;
        while(j<arr.size()){
            if(_map.find(arr[j])==_map.end()){
                _map[arr[j]] = j;
                j++;
                res = max(res, j-i);

            }
            else{
                res = max(res, j-i);
                i = _map[arr[j]]+1;

                _map.clear();

                _map[arr[i]] = i;
                j = i+1;
            }
        }
        return res;
    }
};