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)为下标，数组元素为数字】
二是对字符串进行遍历找出所有子串
可使用双重循环、单循环单指针、双指针【滑动窗口】
注意：代码运行每次速度都不同，估计服务器负载有波动
注意：代码运行每次速度都不同，估计服务器负载有波动
注意：代码运行每次速度都不同，估计服务器负载有波动
-
新手基本型【基本查重+双重循环】，无脑遍历，注定超时
用双重循环遍历所有子串，字符查重则可以采用集合
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
-
下标查重+双重循环，有所改善，超过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 -
字典查重【单判断】+双指针，有所改善，超过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 -
集合查重+双指针，表现良好，超过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 -
集合查重+单循环单指针，有所改善，超过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 -
下标查重+双指针，有所改善，超过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 -
字典查重【双判断】+双指针，表现良好，超过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 -
下标查重+单循环单指针，表现良好，超过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 -
下标查重+单循环单指针跳跃，华山论剑，谁是英雄！
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 ~