题目

longest-substring-without-repeating-characters

算法

哈希：O(n)

• 设立256的哈希数组，初始化为0
• 设置变量res：结果；left：指向该无重复子串的左端
• 遍历数组：
• 若哈希表为0，说明没有遇到过该字符，计算重复字符长度：i-left+1
• 若哈希表数值小于left，说明已经遇到过该数组，重新计算重复子串，left位置更新为，此前出现过的字符
• 每次哈希表中将当前字符对应值，设为i+1

set:O(n)

• 出现过的字符加入set
• 遇到重复，则从左边删除字符，知道删除到没有重复字符为止

代码

* 哈希

class Solution{
    int lengthOfLongSubstring(string s){
        int m[256]={0},res=0,left=0;
        for(int i=0;i<s.size();i++){
            if(m[s[i]]==0 || m[s[i]]<left){
                res=max(res,i-left+1);
            }else{
                left=m[s[i]];
            }
            m[s[i]]=i+1;
        }

        return res;
    }
};

* set

class Solution{
    int lengthOfLongSubstring(string s) {
        set<char> t;
        int res=0,left=0,right=0;
        while(right<s.size()){
            if(t.find(s[right])==t.end()){
                t.insert(s[right++]);
                res=max(res,(int)t.size());
            }else{
                t.erase(s[left++]);
            }


        }

        return res;
    }
};