定长滑动窗口

模板

右指针向右遍历:
    元素进入窗口(增长均值/总和等)
    若窗口尺寸不足:
        右指针继续向右
    否则:
        若满足条件(使题目而定):
            更新答案
        左指针右移,元素离开窗口

例题一

Leetcode 643. 子数组最大平均数 I

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        ans, aver = float("-inf"), 0
        for i in range(len(nums)):
            # right = i
            # right - left + 1 = k
            # left = i - k + 1
            aver += nums[i]
            if i < k - 1:
                continue
            else:
                ans = max(ans, aver)
                aver -= nums[i - k + 1]
        return ans / k

例题二

Leetcode 2090. 半径为 k 的子数组平均值

class Solution:
    def getAverages(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        avgs = [-1] * n
        avg = 0
        for i in range(n):
            # right = i
            # right - left + 1 = 2 * k + 1
            # left = i - 2 * k
            avg += nums[i]
            if i - 2 * k < 0:
                continue
            else:
                avgs[i - k] = avg // (2 * k + 1)
                avg -= nums[i - 2 * k]
        return avgs

例题三

Leetcode 2461. 长度为 K 子数组中的最大和

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        ans = 0
        temp_sum = 0
        window = defaultdict(int)
        for i in range(n):
            temp_sum += nums[i]
            window[nums[i]] += 1
            if i - k + 1 < 0:
                continue
            else:
                if len(window) == k:
                    ans = max(ans, temp_sum)
                temp_sum -= nums[i - k + 1]
                window[nums[i - k + 1]] -= 1
                if window[nums[i - k + 1]] == 0:
                    del window[nums[i - k + 1]]
        return ans

不定长滑动窗口

模板

右指针向右遍历:
    右移左指针直到窗口满足条件:
        左侧元素离开窗口
    右侧元素进入窗口
    # 上面这步也可能出现在循环的最开始
    # 这里演示用集合的做法，先加再删会导致刚加被删
    更新答案

例题一

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

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans = left = 0
        # 哈希表写法
        # cnt = defaultdict(int)
        # for right, ch in enumerate(s):
        #     cnt[ch] += 1
        #     while cnt[ch] > 1:
        #         cnt[s[left]] -= 1
        #         left += 1

        # 哈希集合写法
        window = set()
        for right, ch in enumerate(s):
            # 要先删再加，不然刚加的字符会被删
            while ch in window:
                window.remove(s[left])
                left += 1
            window.add(ch)
            ans = max(ans, right - left + 1)
        return ans

例题二

Leetcode 3090. 每个字符最多出现两次的最长子字符串

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        ans = left = 0
        cnt = defaultdict(int)
        for right, ch in enumerate(s):
            cnt[ch] += 1
            while cnt[ch] > 2:
                cnt[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans