點擊上方「小詹學Python」，選擇「置頂公眾號」
資源乾貨第一時間送達！
寫在前邊：
小詹一直覺得自己編程能力不強，想在網上刷題，又怕不能堅持。不知道有木有和小夥伴和小詹一樣想找個人一起刷題呢？歡迎和小詹一起定期刷leetcode，每周一周五更新一題，每一題都吃透，歡迎一題多解，尋找最優解！歡迎小夥伴們把自己的思路在留言區分享出來噢
前期回顧：
【記錄帖】（No.002）從零打卡刷Leetcode
【記錄帖】（No.001）從零打卡刷Leetcode
上一期有留一個小bug讓小夥伴們找，不知道多少人自己找到了啊？愛學習的人肯定自己去嘗試了，肯定發現leetcode上運行結果發現輸出不是預期的[7, 0, 8]，而是像下邊這樣：
Finished in 36 ms
[7, 0.6999999999999993, 8.07, 1]
一個不合預期的地方是出現了小數，還有一個則是鍊表長度不合預期。其實，這個是除法導致的，這裡的除法保留了小數部分，導致進位標誌carry不是我們需要的整型0或者1了，所以出現了小數，另一方面進位的錯誤也導致在最高位的時候再次進了一位，即鍊表中多出了個1。修改方法很簡單，只需要在兩處carry位置進行類型轉換，具體如下。或者注意''/''和「//」的區別，後者所除的結果僅保留商（整型），前者即存在小數。
carry = int(p.next.val / 10)
上期沒找出原因的小夥伴可以去改過來試試看噢~
No.3 Longest Substring without Repeating Characters
原題：
Given a string, find the length of the longest substring without repeating characters.
題目大意：給出一個字符串，找到最長的沒有重複字符的子字符串，並返回該子字符串的長度。
例如：
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.
可能是前邊的題目都大同小異，難度也接近。也有可能是人的思維有慣性，小詹又是利用循環嵌套遍歷所有情況進行判斷的，這種簡單粗暴可以實現，但是效率很低。大體思路是：第一層循環從字符串的最左側到最右側第二個，即for i in range(0,len(s)-1)，第二層循環則從第一層緊跟著的一個到最後一個字符。即for j in range(i+1,len(s));之後通過找出所有不重複的子字符串，比較長度得到最大長度的子字符串。代碼如下：（需要注意當字符串長度為0或1的特殊情況）
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
max_len = 0
if (len(s) == 1 or len(s) == 0):
max_len = len(s)
for i in range(0,len(s)-1):
for j in range(i+1, len(s)):
if s[j] in s[i:j]:
if j-i > max_len:
right = j
left = i
max_len = right-left
break
elif j == len(s) - 1:
if max_len < j - i + 1:
max_len = j - i + 1
return max_len
結果當然是可以通過的啦，然而時間效率方面很差很差，如圖：
然而，我們不能滿足於這種最低效率的實現結果。下邊提出一個炒雞牛逼的方法，非原創，小詹花了很久才搞明白其思路，其利用到了字典的方法。什麼是字典？請自行補充知識噢（公眾號有語法綜述）。先放代碼後再解釋：
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
indexDict = {}
maxLength = currMax = 0
for i in range(len(s)):
if s[i] in indexDict and i - indexDict[s[i]] - 1 <= currMax:
if maxLength < currMax:
maxLength = currMax
currMax = i - indexDict[s[i]] - 1
currMax = currMax + 1
indexDict[s[i]] = i
return maxLength if currMax < maxLength else currMax
代碼裡對應位置加入了注釋，理解起來應該好很多了，這裡舉例說明下為什麼【i - indexDict[s[i]] - 1】代表了當前找到子字符串的長度。
比如字符串'abcdadd'，代碼運行過程中一直迭代到i=3【對應字符d】時，都不滿足s[i] in indexDict ,不執行條件語句，而是currMax依次加一，並且將字符信息以{s[i]:i}的形式存放在字典中。當繼續迭代i=4時，進入條件語句，這裡主要解釋【i - indexDict[s[i]] - 1】，檢測到了重複字符'a'，之前該字符出現位置為i=0處即【indexDict[s[i]] =0】這時候當前檢測到的無重複字符子串為'abcd'，長度為【4-indexDict[s[i]] -1 = 3】。其他同此例。
Python系列之——在北京當房奴的日子~
反爬蟲和反反爬蟲（下篇）