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

模板题，典型滑动窗口

class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        int n = arr.size();
        // 窗口左右边界
        int l = 0;
        int r = 0;
        // 缓存集合，判断重复
        unordered_set<int> cache;
        // 收缩标志位
        bool flag;
        // 初始最优解
        int len = 0;
        while( r < n){
        
            // 扩展
            int cur_r = arr[r++];
            // 如果当前元素在集合中已经出现过，说明该元素之前的子序列已是局部最优解，该收缩了
            if(cache.count(cur_r))
                flag = true;
            else
                cache.insert(cur_r);
            
            // 收缩
            while(flag){
            	// 如果出现更优解则更新len(注意当前元素的位置为r-1
                if(len < r - 1 - l)
                    len = r - 1 - l;
                int cur_l = arr[l++];
                cache.erase(cur_l);
                // 重复元素已被删除，将目标元素插入集合
                if(!cache.count(cur_r)){
                    flag = false;
                    cache.insert(cur_l);
                }
            }
            
        }
        return len == 0 ? n : len;
        
    }
};