【C++】双指针+map

条件：

1. 设置两个指针/索引，left = 0 right = 1；
2. map<int,int>，记录数组元素的 值-索引： value：index

设定：

1. left到right之间的元素为连续不重复；
2. map中存放left到right间元素的 值-索引 对；
3. 初始left right都在数组首部，从right++进数，从left--出数；
4. 进数： right++，检查map(含连续不重复子序列中所有元素) 中是否存在arr[right]，不存在即不重复，向连续不重复子序列进数，加入map，right继续向前。
5. 出数： left--,以上检查map是否含arr[right]时，若存在，则需要从left段出数，即从map中吐出arr[left]，并left++，直至arr[left]==arr[right]，即一直吐到存在的和当前right所指同值元素。
6. 在每次进数出数的过程中，维护不重复子数组的最大长度maxLength = max{maxLength, map.size()}

整个过程，像蚯蚓一样伸缩爬动至数组末尾，right为头 一直向前吞，left为尾 一直前缩吐数。

/*
    【双指针】
    从右指针进数，从左指针出数

*/
    int maxLength(vector<int>& arr) {
        // write code here
        //invalid input
        if(arr.empty())
            return 0;
        //init
        map<int,int> map;            // value-index
        int left = 0;
        int right = 1;
        map[arr[0]] = 0;
        int maxLength = 0;           //记录最大连续不重复子序列长度

        //假设 left--right 为连续不重复段
        while(left<=right && right<arr.size()){    //[left,right]
            //待加入元素 arr[right]重复，先删除再加入
            if(map.count(arr[right])){
                //从left删除至与arr[right]等值元素
                while(arr[left]!=arr[right]){
                    map.erase(arr[left]);
                    ++left;
                }
                ++left;
            }
            //加入arr[right]
            map[arr[right]] = right;
            maxLength = maxLength<map.size()? map.size():maxLength;
            ++right;
        }
        return maxLength;
    }