双指针。
要注意的是18行left = max(left, index + 1);
一定不要忘记加max
,因为left这次不是一步一步往前走了,是往前跳跃,跳跃的时候有可能直接跳过了未来可能出现的“重复数字”。
class Solution { public: /** * * @param arr int整型vector the array * @return int整型 */ int maxLength(vector<int>& arr) { int len = arr.size(); int left= 0, right = 0, maxlen = 0; unordered_map<int, int> map; while(right < len) { if(map.find(arr[right]) != map.end()) { int index = map.find(arr[right])->second; // 一定要注意这点用max! left = max(left, index + 1); } map[arr[right]] = right; if(right - left + 1 > maxlen) maxlen = right - left + 1; right++; } return maxlen; } };