leetcode3. Longest Substring Without Repeating Characters(最长不重复子串）

秒速五厘米 2022-12-02 10:45 134阅读 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.

**默认第一思路：** 这个思路是我做的时候会第一想到的思路，所以先不看题解。  
为了找到最长不重复子串，重点就是在于处理两个相同的字符不能在同一个区间里面，所以需要用一个hash来保证最快找到上一个相同的字符的位置在哪。可以用dp表示到这个字符的最大不重复子串，也就是动态规划，小问题就是小字符串长度，dp(1)=1, dp(2)就需要看是否之前已经存在，如果已经存在了，就要判断是到上一个的位置长度长还是直接在当前dp\[i-1\] 的子串+1 长，找到最小的哪个就是最有效。

code

class Solution { 
    public:
        //用u_map记录每个字符的pos，然后遍历，用当前pos-（-1）/上一个出现的地方
       
        int lengthOfLongestSubstring(string s) { 
            if(s.size()==0)
                return 0;
            unordered_map<char,int> imap;
            int len=1;
           // vector<int> dp(s.size());
            //dp[0]=1; //第一个字符需要设置进入imap中
            int pre=1,cur=0;
            imap[s[0]]=0;       //否则第一个字符在这之中出现是在后面第二个！并且1个字符结果是0
            for(int i=1;i<s.size();i++){ 
                if( imap.find(s[i])==imap.end()){ 
                    //dp[i]=dp[i-1]+1;
                    cur=pre+1;
                    imap[s[i]]=i;
                    pre=cur;
                }
                else{ 
                   // dp[i]=min(i-imap[s[i]], dp[i-1]+1); //两者相比取较小值
                    cur=min(i-imap[s[i]],pre+1 );   //和前一个相比，是有你没我，有我没你
                    imap[s[i]]=i;   //更新位置
                    pre=cur;
                    
                }
                len=max(cur,len);
            }
            return len;
        }
    };

思路二：  
因为anscii一共可表示256的字符（因为char最大256），所以不需要map了，所以设置数组dict（256，-1）然后开始遍历。如果找到了已经出现的，start位置改变，否则就是当前i-start  
**//为什么不算从当前到上一个相同的位置之间的长度，因为前一个数已经计算过了！**

优化代码：

class Solution { 
    public:
        //用u_map记录每个字符的pos，然后遍历，用当前pos-（-1）/上一个出现的地方
       
        int lengthOfLongestSubstring(string s) { 
           if(s.empty())
               return 0;
            vector<int> dict(256,-1);
            int maxlen=0, start=-1;
            for(int i=0;i<s.size();i++){ 
                if(dict[s[i]] >start )  //说明这个字符出现过了，上一个位置在dict[s[i]]
                    start=dict[s[i]];
                dict[s[i]]=i;
                maxlen=max(maxlen, i-start);    //为什么不算从当前到上一个相同的位置之间的长度，因为前一个数已经计算过了！
            }
            return maxlen;
        }
    };