LeetCode题目总结-滑窗法

LeetCode题目总结-滑动窗口法

滑动窗口法:此方法首先建立一个长度为零的窗口,把右侧窗口向右移动,当新的元素与原来窗口中的元素不重复时,把新的元素加入其中,并更新窗口长度;当新的元素与原集合中的元素重复时,把窗口的左侧向右移动,直至原窗口中的元素不含新的元素。

3.  无重复字符的最长子串

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        if not s:
            return 0
        
        start, end = 0, 0
        res, lookup = 0, set()
        
        while start < len(s) and end < len(s):
            if s[end] not in lookup:  # 最新碰到的字符串中没有出现过
                lookup.add(s[end])    # 记录下当前子串新增的字符
                res = max(res, end-start+1)  # 更新最大长度
                end += 1           # 窗口向后滑动
            else:                  # 新的字符在以前已经出现过了,窗口的左侧从左向右移动,直到原字符串不包含新的字符串
                lookup.discard(s[start])
                start += 1
                
        return res

 

上一篇:c# – 保存相关常量的最佳实践?


下一篇:php – 在MySQL中创建查找表的最快方法