LeetCode力扣_第三題_無重復字符的最長子串

2021-07-10 17:08 作者:啥也不會的小噢 0人讀過 | 我要投稿

第一次寫專欄

原因有倆：一是怕忘故作記錄，當成筆記來記錄；二是激勵自己學習。

廢話不多說，上題：

說是給定一個字符串，找出不含有重復字符的最長字串的長度。

題目很容易理解，給個例子：

輸入: s = "abcabcbb"

輸出: 3?

解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。

答：首先思路是這樣的，因為字串內(nèi)不能有重復的字符，這是個判別條件。最終的目的是返回最長字串的長度。因此需要篩選出字符串內(nèi)所有的不含重復字符的字串，然后計算長度，再得最大值。

????????字串計算長度是首-尾+1，那么這里就是要確定首部和尾部，首部就是遍歷的時候位置，而尾部要保證首尾字串中無重復字符。因此在往前遍歷的時候，若是出現(xiàn)與后面重復的字符的時候，尾部應該調(diào)整到后面重復字符前的一位，再來計算長度。

流程圖：

下面是代碼實現(xiàn)（python3）：

1class?Solution:

2???def?lengthOfLongestSubstring(self,?s:?str)?->?int:

3????????ans=0 %存儲最大字串長度

4?? ?????i=0%尾部

5????????pd={}%字典

6????????for?j?in?range(len(s)): %遍歷字符串

7????????????if?s[j]?in?pd:

8????????????????i=max(pd[s[j]],i) %若是遇見重復字符，調(diào)整到最近的重復字符位置

9????????????ans=max(ans,j-i+1) %計算字串長度，取最大值

10? ? ? pd[s[j]]=j+1 %加入鍵值對

11??????return?ans??

執(zhí)行過程是這樣的：

舉個例子abcabcd：那么遍歷的時候

i：? ? 0 0 0 1 2 3 3

str： a b c a b c d

j：? ? 0 1 2 3 4 5 6

pd[s[j]]:1 2 3 4 5 6 7?

這段代碼是參考別人的解答，個人覺得很好，于是拿來學習下：

????????這里在學習的時候有疑問的地方，第8行，為什么尾部的位置還是重復字符的位置，而不是前面一個字符的位置，在計算長度的時候也是對的，后來發(fā)現(xiàn)是第10行j+1的作用。而且這個+1是有說法的，為了防止“ ”的情況發(fā)生，因為在s=“ ”的時候，輸出的是0，是不對的，按理要輸出1的，是因為range（len（s）)=[0,1),j在遍歷的時候只是遍歷到0，因此輸出的是0。這里+1避免了這種特殊情況發(fā)生。