LeetCode 3. 无重复字符的最长子串（滑动窗口+哈希）

示例 1:
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i, j, k, start = 0, end = 0, maxlen = 0;
        unordered_map<char,int> m;
        unordered_map<char,int>::iterator it;
        for(i = 0; i < s.size(); ++i)
        {
        	it = m.find(s[i]);
        	if(it != m.end())
            {
        	    k = it->second;
        		for(j = start; j <= k; ++j)	//之前没用k存储，erase后，it失效
        			m.erase(s[j]);
        		start = k+1;
        	}
            m[s[i]] = i;
        	++end;
    		if(end-start > maxlen)
    			maxlen = end-start;
        }
        return maxlen;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i, k, start = 0, end = 0, maxlen = 0;
        unordered_map<char,int> m;
        unordered_map<char,int>::iterator it;
        for(i = 0; i < s.size(); ++i)
        {
        	it = m.find(s[i]);
        	if(it != m.end())
        	{
        	    k = it->second;
        		start = max(start, k+1);//不删key，start直接跳到重复的下一个
        	}
            m[s[i]] = i;//更新下标位置
        	++end;
    		if(end-start > maxlen)
    			maxlen = end-start;
        }
        return maxlen;
    }
};

class Solution {	//2020.3.10
public:
    int lengthOfLongestSubstring(string s) {
    	if(s.empty())
    		return 0;
    	set<char> set;
    	int i = 0, j = 0, maxlen = 0;
    	for( ; j < s.size(); ++j)
    	{
    		if(!set.count(s[j]))
    		{
    			set.insert(s[j]);
    			maxlen = max(maxlen,j-i+1);
    		}
    		else
    		{
    			while(s[i] != s[j])
    			{
    				set.erase(s[i++]);
    			}
    			i++;
    		}
    	}
    	return maxlen;
    }
};

class Solution {	//2020.5.2
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> m;
        int maxlen = 0, i = 0, j = 0;
        while(j < s.size())
        {
            m[s[j]]++;
            if(m[s[j]]>1)
            {
                while(m[s[j]]>1)
                {
                    m[s[i]]--;
                    i++;
                }
            }
            else
                maxlen = max(maxlen,j-i+1);
            j++;
        }
        return maxlen;
    }
};