leetcode3. Longest Substring Without Repeating Characters(最长不重复子串）-蒲公英云

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

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;
    }
};