3. 无重复字符的最长子串

题目描述
给定一个字符串，请找出最长的不包含重复字符的子串。
请注意子串和子序列的区别：

子串一定是连续的一段
子序列不一定是连续的一段，但下标要求是递增的
样例
给定 "abcabcbb"，答案是"abc"，长度是3.
给定 "bbbbb"，答案是"b"，长度是1.
给定 "pwwkew"，答案是"wke"，长度是3.

题解

双指针算法：O(n)

class Solution {
public:
    int lengthOfLongestSubstring(string s) 
    {
        unordered_map<char,int>hash;
        int res=0,len=s.size();
        for(int i=0,j=0;j)
        {
            hash[s[j]]++;
            while(hash[s[j]]>1) hash[s[i++]]--;
            res=max(res,j-i+1);
        }
        return res;
    }
};

暴力枚举O(n3)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        if(!s.size())
            return maxLen;
        for(int i = 0; i < s.size(); i++){
            for(int j = 0; j < s.size(); j++){
                if(isUniq(s, i, j))
                    maxLen = max(maxLen, j-i+1);
            }
        }
        return maxLen;
    }
    bool isUniq(string s, int start, int end){
        set<char> uniqSet;
        for(int i = start; i <= end; i++){
            if(uniqSet.count(s[i]))
                return false;
            uniqSet.insert(s[i]);
        }
        return true;
    }
};