题解 | #最长无重复子数组#map记录各个元素出现的位置，遇到重复的如何标记上一个start

class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    /*
        1,使用map记录数组中各个元素出现位置
        2，如果遇到重复的，找到之前的最近的一个重复的值记为index
        则index的下一个到当前的i，中间的距离是候选人
        将ret和[index + 1, i]进行比较大小
        ret ，(i - index)
        3，更新map中的curr的位置
    */
    int maxLength(vector<int>& arr) {
        // write code here
        map<int,int> mp;
        int cnt = 1;
        int start = 0; // start的意思是离i最近的不重复的数字的，画个图更清晰。
        for(int i = 0;i < arr.size();i++){
            // 遍历数组，如果遇到之前填充过的值，找到离i最近的一个重复数字的index
            if (mp.find(arr[i]) != mp.end()) {
                
                start =(start > mp[arr[i]] + 1) ? start : mp[arr[i]] + 1;
            }
            // 记录i到最近的一次重复的距离，并与cnt进行比较
            cnt = max(cnt, i - start + 1);
            // 将curr出现的位置更新为当前值
            mp[arr[i]] = i;
        }
        return cnt;
    }
};