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

看到“最”就要想到动态规划

#include <map>
class Solution {
public:
    /**
     * 
     * @param arr int整型vector the array
     * @return int整型
     */
    int maxLength(vector<int>& arr) {
        // write code here
        if(arr.size() == 0){
            return 0;
        }
        int* d = new int[arr.size()];
        map<int, int> m;
        d[0] = 1;
        m[arr[0]] = 0;
        for(int i = 1 ; i < arr.size(); i++){
            int val = arr[i];
            if(m.find(val) == m.end()){
                m[val] = i;
                d[i] = d[i - 1] + 1;
            }
            else{
                int index = m[val];
                vector<int> remove_list;
                for(map<int, int>::iterator iter = m.begin(); iter != m.end(); iter++){
                    if(index >= iter->second){
                        remove_list.push_back(iter->first);
                    }
                }
                for(int j = 0; j < remove_list.size(); j++){
                    m.erase(remove_list[j]);
                }
                m[val] = i;
                d[i] = m.size();
                
            }
        }
        int max = -1;
        for(int i = 0 ; i < arr.size(); i++){
            if(max < d[i]){
                max = d[i];
            }
        }
        return max;
    }
};