Python算法题集_无重复字符的最长子串

本文为Python算法题集之一的代码示例

题目3：无重复字符的最长子串

说明：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

---

- 感慨：本题很特殊，特别特殊，超级无敌特殊！！！

程序员没有一个没写过字符串处理，没有一个没写过查找字符串子串

问题是谁都能写，可是写出来就是原形毕露，稍不留神，就要贻笑大方

大虾们是高手，十年练剑，深藏不露，都是传说中十步杀一人，千里不留行的人物

如果本文写得笨拙浅薄，还请大虾们多多包涵，高抬贵手~~

---

本题求解有两个重点工作

一是在子串中进行字符查重

可以使用基本查重【集合中查询子元素】、字典查重【哈希值，值为数字】、下标查重【ord(char)为下标，数组元素为数字】

二是对字符串进行遍历找出所有子串

可使用双重循环、单循环单指针、双指针【滑动窗口】

---

注意：代码运行每次速度都不同，估计服务器负载有波动

注意：代码运行每次速度都不同，估计服务器负载有波动

注意：代码运行每次速度都不同，估计服务器负载有波动

---

1. 新手基本型【基本查重+双重循环】，无脑遍历，注定超时

   ​ 用双重循环遍历所有子串，字符查重则可以采用集合set去重查重或者字符串查子串函数查重。此算法颇为无脑，算是初学程序者的作品，肯定会超时，就不给它表现的机会了

   def longest_unique_substr_newbie(s):  # 双循环遍历、集合查重iLen=len(s)iMaxsublen=0for iIdx in range(iLen):for iJdx in range(iIdx+1, iLen-1):if len(set(s[iIdx:iJdx])) == iJdx-iIdx:iMaxsublen = max(iMaxsublen, iJdx-iIdx)return iMaxsublenprint(longest_unique_substr_newbie('abcabcbb'))
   # 运行结果 
   3
   

---

2. 下标查重+双重循环，有所改善，超过77%
   

   def longest_unique_substr_ext1(s):  # 下标查重+双重循环iLen = len(s)iMaxsublen = 0icharcount = [0] * 128ileft, iright = 0, 0while iright < iLen:icharcount[ord(s[iright])] += 1while icharcount[ord(s[iright])] > 1:icharcount[ord(s[ileft])] -= 1ileft += 1iMaxsublen = max(iMaxsublen, iright - ileft + 1)iright += 1return iMaxsublenprint(longest_unique_substr_ext1('abcabcbb'))
   # 运行结果 
   3
   

3. 字典查重【单判断】+双指针，有所改善，超过77%
   

   def longest_unique_substr_ext2(s):  # 字典查重+双指针iLen = len(s)iMaxsublen = 0dictwindow = {}ileft, iright = 0, 0while iright < iLen:if s[iright] in dictwindow:ileft = max(ileft, dictwindow[s[iright]] + 1)dictwindow[s[iright]] = irightiMaxsublen = max(iMaxsublen, iright - ileft + 1)iright += 1return iMaxsublenprint(longest_unique_substr_ext2('abcabcbb'))
   # 运行结果 
   3
   

4. 集合查重+双指针，表现良好，超过87%
   

   def longest_unique_substr_ext3(s):  # 集合查重+双指针iLen=len(s)iMaxsublen, ileft, iright = 0, 0, 0set_substr = set()while iright<iLen:if s[iright] in set_substr:set_substr.remove(s[ileft])ileft += 1else:set_substr.add(s[iright])iMaxsublen = max(iMaxsublen, iright-ileft+1)iright+=1return iMaxsublenprint(longest_unique_substr_ext3('abcabcbb'))
   # 运行结果 
   3
   

5. 集合查重+单循环单指针，有所改善，超过77%
   

   def longest_unique_substr_ext4(s):  # 集合查重+单循环单指针iLen = len(s)iMaxsublen = 0set_substr = set()istart = 0for iIdx in range(iLen):while s[iIdx] in set_substr:set_substr.remove(s[istart])istart += 1set_substr.add(s[iIdx])iMaxsublen = max(iMaxsublen, iIdx - istart + 1)return iMaxsublenprint(longest_unique_substr_ext4('abcabcbb'))
   # 运行结果 
   3
   

6. 下标查重+双指针，有所改善，超过76%
   

   def longest_unique_substr_ext5(s):  # ASC码下标定位，双指针iLen = len(s)iMaxsublen = 0char_index = [-1] * 128ileft, iright = 0, 0while iright < iLen:if char_index[ord(s[iright])] >= ileft:ileft = char_index[ord(s[iright])] + 1char_index[ord(s[iright])] = irightiMaxsublen = max(iMaxsublen, iright - ileft + 1)iright += 1return iMaxsublenprint(longest_unique_substr_ext5('abcabcbb'))
   # 运行结果 
   3
   

7. 字典查重【双判断】+双指针，表现良好，超过87%
   

   def longest_unique_substr_ext6(s):  # 字典查重+双指针iLen = len(s)iMaxsublen = 0dictwindow = {}ileft, iright = 0, 0while iright < iLen:if s[iright] in dictwindow and dictwindow[s[iright]] >= ileft:ileft = dictwindow[s[iright]] + 1dictwindow[s[iright]] = irightiMaxsublen = max(iMaxsublen, iright - ileft + 1)iright += 1return iMaxsublenprint(longest_unique_substr_ext6('abcabcbb'))
   # 运行结果 
   3
   

8. 下标查重+单循环单指针，表现良好，超过88
   

   def longest_unique_substr_ext7(s):  # 下标查重+单循环单指针iLen = len(s)iMaxsublen, istart = 0, 0dictwindow = {}for iIdx in range(iLen):if s[iIdx] in dictwindow and dictwindow[s[iIdx]] >= istart:istart = dictwindow[s[iIdx]] + 1dictwindow[s[iIdx]] = iIdxiMaxsublen = max(iMaxsublen, iIdx - istart + 1)return iMaxsublenprint(longest_unique_substr_ext7('abcabcbb'))
   # 运行结果 
   3
   

9. 下标查重+单循环单指针跳跃，华山论剑，谁是英雄！
   

   def longest_unique_substr_ext8(s):  # 下标查重+单循环单指针iLen = len(s)iMaxsublen, istart = 0, 0listchar = [-1] * 128for iIdx in range(iLen):if listchar[ord(s[iIdx])] >= istart:istart = listchar[ord(s[iIdx])] + 1listchar[ord(s[iIdx])] = iIdxiMaxsublen = max(iMaxsublen, iIdx - istart + 1)return iMaxsublenprint(longest_unique_substr_ext8('abcabcbb'))
   # 运行结果 
   3
   

   一日练，一日功，一日不练十日空

   may the odds be ever in your favor ~