【python-leetcode03-滑动窗口法】无重复字符的最大子串

概述问题描述： 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb"输出: 3 解释: 因为无重复字

问题描述：

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

示例 1:

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

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

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

按照惯例，首先是我们的简单版滑动窗口法：

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

结果：

虽然有点惨，但好歹先把它做出来了。 

总结

以上是内存溢出为你收集整理的【python-leetcode03-滑动窗口法】无重复字符的最大子串全部内容，希望文章能够帮你解决【python-leetcode03-滑动窗口法】无重复字符的最大子串所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。