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