1.滑动窗口

补:滑动窗口问题可枚举右端点,滑动左端点。

模板

# 窗口的左右边界
class solution:
    def Solution():
        l,r=0,0 # 窗口左右边界
        ans=0
        while r<n:
            # Other Code
            while 判断条件 and l<=r:
                # Other Code
                l+=1
            r+=1
         return ans

例题一

力扣713:

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        ans, left, cur = 0, 0, 1
        for right, num in enumerate(nums):
            cur *= num
            print(cur)
            # 当前到右指针的连乘太大,需要一直挪动左指针直到小于k
            while left <= right and cur >= k:
                cur //= nums[left]
                left += 1
            # 在left到right之间的i, nums[i:right+1]的连乘都满足小于k
            # 知道这个很重要,也是本题的重点
            ans += right - left + 1
        return ans

例题2

力扣3

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
      # 哈希集合,记录每个字符是否出现过,这题重点就是使用集合
        occ = set()
        n = len(s)
        # 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                # 左指针向右移动一格,移除一个字符
                occ.remove(s[i - 1])
            while rk + 1 < n and s[rk + 1] not in occ:
                # 不断地移动右指针
                occ.add(s[rk + 1])
                rk += 1
            # 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1)
        return ans