题目

原题链接

描述

给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。
要求：空间复杂度O(n)，时间复杂度O(nlogn)

思路和算法

本题可以使用双指针+记忆化滑动窗口+哈希表解决。
使用左右指针left、right分别标记滑动窗口的左右边界，使用计数器maxLen、len分别存储目前为止最长子串的长度和当前滑动窗口所表示的子串的长度，同时使用哈希表存储已经遍历过的字符，键为字符本身，值为字符在字符串中的下标。
对于每个当前滑动窗口，检查右边界right所指向的字符是否已经遍历过了。如果已经遍历过了，再检查其位置是否大于等于左边界left，也即，上一个与该字符相同的字符是否在当前滑动窗口中，或者说当前滑动窗口所表示的子串，是否包含重复字符：
1.如果已遍历过但不在当前滑动窗口中，则右指针加一，len值加一，同时更新该字符的哈希值为当前位置；
2.如果已遍历过且位置位于当前滑动窗口中，则更新maxLen，更新左指针的位置为该字符原哈希值加一，更新len值，更新该字符哈希值为新位置，右指针加一；
3.如果未遍历过，则新增该字符记录，滑动窗口长度加一，右指针加一。
至右指针到达字符串边界时，最后一次更新maxLen并返回。

代码

class Solution {//解决方案类
    //因判例数量巨大，使用静态变量节省空间
    static int m;//存储字符串长度，避免反复调用arr.size()造成较大开销
    static int maxLen;//存储答案
    static int left;//左指针
    static int right;//右指针
    static int len;//记录当前滑动窗口长度
    static unordered_map<int,int> map;//记录已遍历数字
public://公有成员
    int maxLength(vector<int>& arr) {//寻找数组arr中的最长不重复子数组长度
        m = arr.size();//数组长度
        maxLen = 0;//答案初始化为零
        left = 0;//左指针初始化为零
        right = 0;//右指针初始化为零
        len = 0;//当前滑动窗口长度初始化为零
        map.clear();//字符串哈希map初始化清空
        while(right<m){//当右指针不为m
            if(map.count(arr[right])){//判断右指针指向的当前数字是否出现过
                if(map[arr[right]]<left){//如果确实出现过但是位置处于左指针左边，不在滑动窗口中
                    len++;//则滑动窗口长度加一
                    map[arr[right]] = right;//同时更哈希map中该字符的位置
                    right++;//右指针加一扩大滑动窗口
                }
                else{//如果该数字已经出现过，且位于当前滑动窗口中
                    maxLen = max(maxLen,len);//则更新答案
                    //一般说来按常规理解应该是更新左指针变动滑动窗口才能更新当前滑动窗口长度，
                    //但是这里为了便于执行进行了相反的操作，不影响算法正确性
                    len -= map[arr[right]]-left;//更新滑动窗口长度
                    left = map[arr[right]]+1;//将左指针置于该数字原位置的右边一个位置
                    map[arr[right]] = right;//更新该数字最新位置
                    right++;//右指针加一
                }
            }
            else{//如果该数字未曾出现过
                map[arr[right]] = right;//则新增该数字记录
                len++;//滑动窗口长度加一
                right++;//右指针加一
            }
        }
        maxLen = max(maxLen,len);//最后一次更新答案
        return maxLen;//返回答案
        

    }
};
//因判例数量巨大，使用静态变量节省空间
//静态变量初始化
int Solution::m = 0;//初始化记录数组长度的int变量
int Solution::maxLen = 0;//初始化存储答案的int变量
int Solution::left = 0;//初始化存储左指针的int变量
int Solution::right = 0;//初始化存储右指针的int变量
int Solution::len = 0;//初始化存储当前滑动窗口长度的int变量
unordered_map<int,int> Solution::map;//初始化存储已遍历数字及其最新位置的unordered_map<int,int>变量

复杂度分析

时间复杂度： O(n)。只需对字符串遍历一遍即可。
空间复杂度： O(n)。用于记录已遍历字符。

可可爱爱的蕾姆镇