剑指offer 面试题48. 最长不含重复字符的子字符串

面试题48. 最长不含重复字符的子字符串

请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。

示例 1:

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

示例 2:

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

示例 3:

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        /*
       // 滑动窗口
       unordered_setchar windows;
       int head=0;
       int tail=0;
       int max_len=0;
       if(s.size()==0)  return 0;
       bool repeat = false;
       while(tail=s.size()-1)
       {
         if(windows.find(s[tail]) != windows.end())   // 说明查到  
         {
            while(true)
            {
                windows.erase(s[head]);  
                if(s[head++]==s[tail])  
                break;
            }
            repeat=true;
         }
        windows.insert(s[tail]);
        if(!repeatwindows.size()max_len)  
           max_len = windows.size();
        tail++;
        repeat=false;
       }
       return max_len;
       */

        unordered_mapchar, int m;
        int ret = 0, l = 0, r = 0;
        while (r  s.size()) {
            if (m.find(s[r]) != m.end()) {
                l = max(l, m[s[r]] + 1);    // 如果重复   则跳到重复位置后一位 
            }
            m[s[r++]] = r;     // 插入s[r]  如果重复 则忽略  如果是新元素则插入   如果是重复的元素  则改变index  
            ret = max(r - l, ret);
        }
        return ret;
    

    }
};
最新回复(0)
/jishuLKi8V_2B3Gd6UBUSVtAIQ0a9kJfuRo3a4nObrwIfaADOU_3D4858767
8 简首页