題目：

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

解題思路：

　　這個(gè)題讓找一個(gè)字符串中具有不重復(fù)單詞的最長(zhǎng)子串的長(zhǎng)度，如：ababc，子串為abc，長(zhǎng)度為3。有這么幾個(gè)方法：

方法一：

　　依賴字符串本身的一些特有函數(shù)，進(jìn)行相應(yīng)操作來完成。我們可以維護(hù)一個(gè)子串，來保存最長(zhǎng)的無重復(fù)的子串，并記錄當(dāng)前子串的長(zhǎng)度，如果遇到重復(fù)的字符，則去掉子串中重復(fù)的字符，一次進(jìn)行下去，最終就能找到最長(zhǎng)無重復(fù)子串。如str = ababc, substr = a, ab, ba, ab, abc....類似這樣的思路。如下代碼：

//方法一：string only int lengthOfLongestSubstring(string s) {size_t j = 1;if (s.size() <= 1)return s.size();int len = 1, nMaxLen = 0;string subStr;subStr.push_back(s[0]);while (j < s.size()) {if (subStr.find(s[j]) == string::npos) {subStr.push_back(s[j]);}else {if (len > nMaxLen)nMaxLen = len;while (subStr.find(s[j]) != string::npos) {subStr.erase(0,1);len --;}subStr.push_back(s[j]);}len ++;j ++;}if (len > nMaxLen)nMaxLen = len;return nMaxLen; }

?

方法二：

　　指針法：用一個(gè)指針指向字符串的左邊界，如果遇到重復(fù)的字符，就往后移動(dòng)，同時(shí)用一個(gè)有26位的字符數(shù)組（因?yàn)榭偣簿?6個(gè)字符）來保存每一個(gè)字符最近一次出現(xiàn)的位置，以此來更新指針位置和字符位置之間的距離，就可以算出最長(zhǎng)無重復(fù)字符的長(zhǎng)度，如下代碼所示：

1 //方法二：pointer 2 int lengthOfLongestSubstring2(string s) { 3 int maxlen = 0, left = 0; 4 int sz = s.length(); 5 int prev[26]; 6 memset(prev, -1, sizeof(prev)); 7 8 for (int i = 0; i < sz; i++) { 9 if (prev[s[i]-'a'] >= left) { 10 left = prev[s[i]-'a'] + 1; 11 } 12 prev[s[i]-'a'] = i; 13 maxlen = max(maxlen, i - left + 1); 14 } 15 return maxlen; 16 }

?

方法三：

　　hashtable法：該方法和方法二其實(shí)是同一個(gè)思路，只不過該方法我不用數(shù)組來存字符的位置，而是通過hashtable來存，進(jìn)而提高效率。如下代碼：

1 //方法三：hash table 2 int lengthOfLongestSubstring3(string s) { 3 if(s.length()<2) 4 return s.length(); 5 int max_len=0; 6 map<char,int> sub; //hash map 7 for(int i=0,j=0;i<s.length();++i){ 8 if(sub.find(s[i])!=sub.end()){ 9 j=max(j,sub[s[i]]+1); 10 } 11 sub[s[i]]=i; 12 max_len=max(max_len,i-j+1); 13 } 14 return max_len; 15 }

?

總結(jié)

以上是生活随笔為你收集整理的LeetCode: 3_Longest Substring Without Repeating Characters | 求没有重复字符的最长子串的长度 | Medium...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。