Longest Substring Without Repeating Characters 子字符串的最大不重复长度

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

滑动窗口问题,比如abcabcbb,滑动到abca的时候需要丢弃第一个a变成bca,继续向右滑动,每次滑动都要检查有没有重复.感觉涉及到最大,最多的问题都可以试着网哈希表上靠.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int size = s.size();
        if (size == 0)
            return 0;
        //这里也可以用 map<int,int> m;256是因为char为8字节,2的8次方
        vector<int> m(256,0);
        int res = 0;
        int left = 0;
        for (int i=0;i < size;i++)
        {
            //left < m[s[i]] 条件的原因为:当left在哈希表存储值的右边时候,哈希表存储的值就应该失效
            if (m[s[i]] == 0 || left > m[s[i]])
            {
                res = max(res,i-left+1);
            }
            else 
            {
                left = m[s[i]];
            }
            //i+1是下次出现相同char时候的left(丢弃前i个)
            m[s[i]] = i + 1;
        }
        return res;
    }
};
 
comments powered by Disqus