力扣100题-滑动窗口

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

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

思路一：

• 首先子串是连续的，可以先固定左端点，右端点在数组里遍历，当右端点的数出现过（哈希表），就移动对应的左端点直到满足右端点没有出现过。这样就遍历了所有的可能性，得出最大的ans。这是一个变长的滑动窗口。
• 代码：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 0
        hash = set() # 哈希表
        l = 0
        for r, cur in enumerate(s):
            while cur in hash: #使[l,r]没有重复字符
                hash.remove(s[l])
                l += 1
            hash.add(cur)
            ans = max(ans, r - l + 1)
        return ans

2.找到字符串中所有字母异位词

• 描述：给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

  异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

思路一：

• 由于p是确定的，这是一个定长的滑动窗口，用一个26大小的list来记录p，每一移动减少一个字母增加一个字母，再判断当前窗口是否和p一致即可。
• 代码：

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        slen = len(s)
        plen = len(p)
        if slen < plen:
            return []
        s_count = [0] * 26
        p_count = [0] * 26 #list初始化
        ans = list()
        for i in range(plen):
            s_count[ord(s[i])-97] += 1
            p_count[ord(p[i])-97] += 1 #对第一个plen的子串进行特殊处理
        if s_count == p_count:
            ans.append(0)
        for i in range(plen, slen):
            s_count[ord(s[i - plen])-97] -= 1
            s_count[ord(s[i])-97] += 1 #移出一个字母，移进一个字母
            if s_count == p_count:
                ans.append(i-plen+1)
        return ans

小节：

• 滑动窗口是指维护一个满足特殊条件的区间，可能是定长的或是变长的
• 重点是这个特殊条件，以上两个条件分别是没有重复字母（哈希表），判断是否是某个字符串的异位词（数组标记）
• 有点像双指针，是一种特殊的双指针策略，主要用于处理连续子数组或子字符串问题。第一题就是它通过维护一个动态的区间（窗口）来优化查找过程。