問題描述：

Given a string, find the length of the?longest substring?without repeating characters.

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.

給出一個字符串，找到它的最長無重復(fù)子序列長度。

思路1

從下標(biāo)0開始，依次查找以當(dāng)前下標(biāo)開始的最長不重復(fù)子序列。

舉例說明：

C++代碼實(shí)現(xiàn)：

int GetMaxLength(string& sTemp, int startIndex) {map<char, int> mapChar;int max = 0;for (int i = startIndex; i < sTemp.length(); ++i){if (mapChar.find(sTemp[i]) != mapChar.end())return max;mapChar[sTemp[i]] = i;++max;}return max; }int lengthOfLongestSubstring(string s) {int max = 0;for (int i = 0; i < s.length(); ++i){int temp = GetMaxLength(s, i);if (temp > max)max = temp;}return max; }

?

思路2

設(shè)當(dāng)前檢測的子序列，下標(biāo)最小值為m，最大值為n（即子串strInput[m,n]），則當(dāng)前檢測序列的長度為n-m+1。

如果該序列中沒有重復(fù)元素，那么它的長度可以作為最長無重復(fù)子序列長度的一個候選值（如果后來有的序列長度超過了它，就替換掉）

我們設(shè)當(dāng)前檢測序列的起始下標(biāo)為now，遍歷整個字符串，遍歷中當(dāng)前下標(biāo)為i；如果可以保證從now到i中沒有重復(fù)元素，遍歷一次，就可以利用i-now+1找到最長無重復(fù)子序列。

使now從0開始，后移遍歷下標(biāo)i，直到strInput[now,i]中出現(xiàn)重復(fù)的字符，更新now的值，將now移動到重復(fù)字符第一次出現(xiàn)的下標(biāo)后即可。

舉例說明：

可以將字符和下標(biāo)存入哈希表中，這樣在查找新加入的字符是否在原始檢索串中存在時，時間復(fù)雜度為1。

C++代碼實(shí)現(xiàn)：

int lengthOfLongestSubstring(string s) {int maxLength = 0;int now = 0;map<char, int> charMap;for (int i = 0; i < s.length(); ++i){if (charMap.find(s[i]) != charMap.end()){now = charMap[s[i]] + 1 > now ? charMap[s[i]] + 1 : now;}if (i - now + 1>maxLength){maxLength = i - now + 1;}charMap[s[i]] = i;}return maxLength; }

思路2優(yōu)化

由于在C++中字符和數(shù)字轉(zhuǎn)換非常簡單，所以，可以用一個數(shù)組來替代哈希表：

C++代碼實(shí)現(xiàn)：

int lengthOfLongestSubstring(string s) {int maxLength = 0;int now = 0;int charMap[256];for (int i = 0; i < 256; ++i){charMap[i] = -1;}const char *p = s.c_str();for (int i = 0; i < s.length(); ++i){if (charMap[p[i]] != -1){now = charMap[p[i]] + 1 > now ? charMap[p[i]] + 1 : now;}if (i - now + 1>maxLength){maxLength = i - now + 1;}charMap[p[i]] = i;}return maxLength; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhaogl/p/6364654.html

總結(jié)

以上是生活随笔為你收集整理的Longest Substring Without Repeating Characters(最长不重复子序列求解)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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