美文网首页
3. Longest Substring Without Rep

3. Longest Substring Without Rep

作者: yunmengze | 来源:发表于2018-09-16 13:37 被阅读0次

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


    Example 1:

    Input: "abcabcbb"
    Output: 3 
    Explanation: The answer is "abc", with the length of 3. 
    

    寻找字符串没有重复字符的最长字串,可以用一个start指针指向字串的开始,用一个字典存储所有遍历过的字符的下标。遍历字符串的时候将当前的字串的长度和记录的字串的长度比较,获得最优的字串的长度。

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int maxLen = 0;
            int beginIndex = 0;
            map<char, int> charIndex;
            int len = s.size();
            for(int i=0; i < len; i++){
                if(charIndex.find(s[i]) == charIndex.end() || charIndex[s[i]] < beginIndex){
                    charIndex[s[i]] = i;
                    maxLen = max(maxLen, i-beginIndex+1);
                }
                else{
                    beginIndex = charIndex[s[i]]+1;
                    charIndex[s[i]] = i;
                }
            }
            return maxLen;
        }
    };
    

    相关文章

      网友评论

          本文标题:3. Longest Substring Without Rep

          本文链接:https://www.haomeiwen.com/subject/yfzxnftx.html