最長(zhǎng)不重復(fù)子串

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.

大致意思：給一個(gè)字符串，找到最長(zhǎng)子串的長(zhǎng)度，要求該子串不包含重復(fù)的字符。

常規(guī)解法：用哈希表來(lái)進(jìn)行查找，這樣查找效率會(huì)高些。從字符串頭部開(kāi)始計(jì)算子串，將沒(méi)有重復(fù)出現(xiàn)的字符存入哈希表中，如果遇到相同的字符，表明當(dāng)前不重復(fù)子串已經(jīng)結(jié)束，記錄此不重復(fù)子串的長(zhǎng)度，并從哈希表中查到的該重復(fù)字符位置開(kāi)始重新計(jì)算子串，比較確定此子串是否是當(dāng)前最長(zhǎng)的，遍歷整個(gè)字符串后得到不重復(fù)字符的最長(zhǎng)子串長(zhǎng)度。

class Solution {
public:
   int lengthOfLongestSubstring(string s) {
       unordered_map<char, int> m;
       int maxLen = 0;
       int start = -1;
       
       for(int i=0; i<s.size(); i++) {
           auto it = m.find(s[i]);
           if((it != m.end()) && (it->second >= start)) {
               start = it->second;
           }
           m[s[i]] = i;
           maxLen = max(maxLen, i-start);
       }
       
       return maxLen;
   }
};

其他解法：上面用哈希表進(jìn)行查詢雖然相比常規(guī)查詢要節(jié)省時(shí)間，但是我們還可以通過(guò)更簡(jiǎn)潔的方法來(lái)實(shí)現(xiàn)。我們可以用一種更巧妙的方法，因?yàn)橐粋€(gè)字符占一個(gè)字節(jié)，八位，字符的ascii范圍是在256范圍內(nèi)的，我們可以建立一個(gè)256大小的數(shù)組，每次字符的查詢可以直接通過(guò)數(shù)組元素地址直接尋址，每一個(gè)數(shù)組元素的下標(biāo)就是該字符的ascii值，該數(shù)組元素的值是該字符出現(xiàn)在字符串中的位置，每次遍歷字符串中的字符，如果沒(méi)出現(xiàn)重復(fù)則元素為默認(rèn)值，累計(jì)字符串長(zhǎng)度，如果出現(xiàn)重復(fù)則將元素值置為當(dāng)前字符位置，并且重新計(jì)算長(zhǎng)度，這樣依次遍歷完，計(jì)算出最長(zhǎng)子串長(zhǎng)度，時(shí)間復(fù)雜度會(huì)更低。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxlen=0;
        int start=-1;
        vector<int> vt(256,-1);
        for(int i=0;i<s.size();++i)
        {
            if(vt[s[i]]>start)
            {
                start=vt[s[i]];
            }
            vt[s[i]]=i;
            maxlen=max(maxlen,i-start);
        }
        return maxlen;
    }
};