【python-leetcode03-滑动窗口法】无重复字符的最大子串
问题描述: 给定一个字符串,请你找出其中不含有重复字符的?最长子串?的长度。 示例?1: 输入: "abcabcbb" 输入: "bbbbb" 输入: "pwwkew" 按照惯例,首先是我们的简单版滑动窗口法: class Solution: def lengthOfLongestSubstring(self,s: str) -> int: tmp = 0 #用于记录满足条件得最大值 for i in range(1,len(s)+1):步长从1到len(s)+1 for j in range(len(s)-i+1):窗口左端 if len(set(s[j:j+i])) == len(s[j:j+i]):如果取集合后的长度和原始窗口长度一样,说明这个窗口是不含重复字符的 tmp = max(tmp,i)更新tmp的值 return tmp 最后返回即可 看下结果,依旧超时,不过呢: 只有一个用例没通过,如果想要把题目做出来,简单版的滑动窗口,简单粗暴。 要想通过就得使用升级版的滑动窗口了:一个左边界start,一个记录最大值max_num,一个记录当前遍历得子串hash。从左开始遍历数组,先将其加入到hash中,接下来如何判断是否出现了重复得字符呢?想了有点久,想到一种巧妙得办法,如果hash表中得键得长度小于hash表中值得和,说明出现了重复的字符,此时左边界就起作用了,让左边界对应的字符在hash中的值减一,如果还有重复的,start+=1,在执行减一操作,如果该字符值变为0,就将其删除,直到hash表中的键的长度等于值得和,此时记录下当前符合的最大值。 int: if len(s) == 0: return 0 if len(s) == 1: return 1 start = 0 滑动窗口左端 max_num = 0 用于计算最大值 from collections import defaultdict hash = defaultdict(int) in range(len(s)): hash[s[i]]+=1 while len(hash)<self.dictSum(hash): hash[s[start]] -= 1 if hash[s[start]] == 0: del hash[s[start]] start += 1 max_num = max(max_num,i-start+1) max_num def dictSum(self,dic): sum = dic: sum += dic[i] return sum 结果: 虽然有点惨,但好歹先把它做出来了。? (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |