Python算法-滑动窗口（Sliding Window）

滑动窗口

• 1 减少while循环
• 2 数组定长问题

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

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

• 哈希表+双指针

# 双指针
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        right = 0
        result = 0
        window = {}

        while right < len(s):
            if s[right] not in window:
                window[s[right]] = 1
            else:
                window[s[right]] += 1
            # 缩减窗口
            while window[s[right]] > 1:
                window[s[left]] -= 1
                left += 1
            # 维护一个最大值
            result = max(result, right - left + 1)
            right += 1
        return result

209. 长度最小的子数组

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

# 双指针
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        right = 0
        window_sum = 0
        result = len(nums) + 1

        while right < len(nums):
            window_sum += nums[right]
            while window_sum >= target:
                result = min(result, right-left+1)
                window_sum -= nums[left]
                left += 1

            right += 1
        if result != len(nums) + 1:
            return result
        else:
            return 0

713. 乘积小于K的子数组

给定一个正整数数组 nums和整数 k 。
请找出该数组内乘积小于 k 的连续的子数组的个数。

输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。

输入: nums = [1,2,3], k = 0
输出: 0

# 双指针
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0
        left = 0
        right = 0
        window_sum = 1
        result = 0

        while right < len(nums):
            window_sum *= nums[right]
            # 区间左侧边界向右
            while window_sum >= k:
                window_sum /= nums[left]
                left += 1

            # 区间右侧边界向右
            result += (right-left+1)   
            right += 1
        return result

1343. 大小为 K 且平均值大于等于阈值的子数组数目

输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3
解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。

# 滑动窗口
class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        left = 0
        right = 0
        window_sum = 0
        result = 0

        while right < len(arr):
            # 更新窗口内数的求和
            window_sum += arr[right]
            if right - left + 1 >= k:
                # 判断窗口内数的和与平均值的和
                if window_sum >= k*threshold:
                    result += 1
                # 窗口左边界向右移动
                window_sum -= arr[left]
                left += 1 
            # 窗口右边界向右移动
            right += 1
        return result

643. 子数组最大平均数 I

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        result = 1
        count = 1
        for i in range(len(nums)-1):
            if nums[i] < nums[i+1]:
                count += 1
            else:
                count = 1
            result = max(result, count)
        return result

674. 最长连续递增序列

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        result = 1
        count = 1
        for i in range(len(nums)-1):
            if nums[i] < nums[i+1]:
                count += 1
            else:
                count = 1
            result = max(result, count)
        return result

• 双指针

# 双指针
class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        left = 0
        right = 0
        length = len(nums)
        result = 0
        for i in range(length):
            if nums[i] > nums[right]:
                right += 1
            else:
                left = i
                right = i
            result = max(result, right-left+1)
        return result

1004. 最大连续1的个数 III

输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        left = 0
        right = 0
        result = 0
        count = 0

        while right < len(nums):
            # 右边界右移
            if nums[right] == 0:
                count += 1
            right += 1
            # 左边界右移
            if count > k:
                if nums[left] == 0:
                    count -= 1
                left += 1
            # 更新最大值
            result = max(result, right-left)
        return result

1423. 可获得的最大点数

输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。

# 使用固定长度的滑动窗口
# 由于只能从开头或末尾位置拿 k 张牌，则最后剩下的肯定是连续的 len(cardPoints) - k 张牌。
# 要求求出 k 张牌可以获得的最大收益，我们可以反向先求出连续 len(cardPoints) - k 张牌的最小点数。
# 则答案为 sum(cardPoints) - min_sum。
class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        left = 0
        right = 0
        length = len(cardPoints)
        card_sum = sum(cardPoints)
        min_sum = card_sum
        window_size = length - k       # 窗口大小
        window_sum = 0
        if length == k:
            return card_sum

        while right < length:
            window_sum += cardPoints[right]
            if right - left + 1 >= window_size:
                min_sum = min(min_sum, window_sum)
                window_sum -= cardPoints[left]
                left += 1

            right += 1
        return card_sum - min_sum

1052. 爱生气的书店老板

今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意。

输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

# 滑动窗口
# 窗口大小 X
# 固定长度的滑动窗口题目。我们可以维护一个窗口大小为 minutes 的滑动窗口。
# 使用 window_count 记录当前窗口内生气的顾客人数。
# 然后滑动求出窗口中最大顾客数，然后累加上老板未生气时的顾客数，就是答案。
class Solution:
    def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
        left = 0
        right = 0
        result = 0
        window_sum = 0

        while right < len(customers):
            # 求窗口内最多的生气顾客数
            if grumpy[right] == 1:
                window_sum += customers[right]
            # 窗口左边界右移
            if right - left + 1 > minutes:
                if grumpy[left] == 1:
                    window_sum -= customers[left]
                left += 1
                
            right += 1
            result = max(result, window_sum)
            # print(result)

            # 求没有生气的顾客数量
        for i in range(len(customers)):
            if grumpy[i] == 0:
                result += customers[i]
        return result

1456. 定长子串中元音的最大数目

给你字符串 s 和整数 k 。
请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。
英文中的 元音字母 为（a, e, i, o, u）。
输入：s = "abciiidef", k = 3
输出：3
解释：子字符串 "iii" 包含 3 个元音字母。

# 定长窗口
class Solution:
    def maxVowels(self, s: str, k: int) -> int:
        hashmap = ['a','e','i','o','u']
        left = 0
        right = 0
        count = 0
        result = 0

        while right < len(s):
            if s[right] in hashmap:
                count += 1
            if right - left + 1 > k:
                if s[left] in hashmap:
                    count -= 1
                left += 1

            result = max(result, count)
            right += 1
        return result

567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

# 排列关系如何处理？
# 用 collections.Counter() 实现对数组中元素个数的统计

import collections 
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        left = 0
        right = 0
        s1_count = collections.Counter(s1)
        window_count = collections.Counter()
        window_size = len(s1)

        while right < len(s2):
            window_count[s2[right]] += 1
            # 窗口变小
            if right - left + 1 >= window_size:
                if window_count == s1_count:
                    return True
                window_count[s2[left]] -= 1
                if window_count[s2[left]] == 0:
                    del window_count[s2[left]]
                left += 1
            right += 1
        return False

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

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

# 字典+滑动窗口
import collections
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # 创建数组p的字典
        p_dict = collections.defaultdict(int)
        for i in p:
            p_dict[i] += 1
        # 变量初始化
        left = 0
        right = 0
        # 创建滑动窗口的字典
        window_dict = collections.defaultdict(int)
        window_size = len(p)
        count = 0              # 统计相同字符的个数
        result = []
        # 滑动窗口实现
        while right < len(s):
            if s[right] in p_dict:
                window_dict[s[right]] += 1
                if window_dict[s[right]] == p_dict[s[right]]:
                    count += 1
            # 窗口左边界右移
            if right - left + 1 >= window_size:
                # 如果窗口内元素形成的字典与目标数组的字典相等
                if count == len(p_dict):
                    result.append(left)
                # 还要考虑窗口左边界右移是否会移除目标元素
                if s[left] in p_dict:
                    if window_dict[s[left]] == p_dict[s[left]]:
                        count -= 1
                    window_dict[s[left]] -= 1
                left += 1
            right += 1
        return result

995. K 连续位的最小翻转次数（困难）

在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。
返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。

输入：A = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        result = 0
        flip_count = 0
        for i in range(len(nums)):
            # 如果 i - k >= 0，并且 nums[i - k] == 2，需要缩小窗口，将翻转次数减一。
            # （此时窗口范围为 [i - k + 1, i - 1]）
            if i - k >= 0 and nums[i-k] == 2:
                flip_count -= 1
            # 如果 (flip_count + nums[i]) % 2 == 0，则说明 nums[i] 还需要再翻转一次，
            # 将 nums[i] 标记为 2，同时更新窗口内翻转次数 flip_count 和答案最小翻转次数 ans。
            if (flip_count + nums[i])%2 == 0:
                if i + k > len(nums):
                    return -1
                nums[i] = 2
                flip_count += 1
                result += 1
        return result

例题

209：长度最小的子数组
输入：s = 7 , nums=[2,3,1,2,4,3]
输出：2 （找出该数组中满足其和 >= s 的长度最小的 连续子数组，返回其长度）
解释：子数组[4,3]是该条件下的长度最小的子数组

def findSub(s, nums):
    if nums == None or len(nums) == 0:
        return 0

    res = len(nums) + 1
    total = 0          # 子数组的和
    i = 0
    j = 0
    while j < len(nums):
        total = total + nums[j]             # 右指针向右滑动
        j = j + 1
        while total >= s:
            res = min(res, j-i)              # 注意是 j - i
            total = total - nums[i]        # 左指针向右移动
            i = i + 1
    if res == len(nums) + 1:           # 给定一个不可能的值，表示没找到
        return 0
    else:
        return res

s = 7 
nums=[2,3,1,2,4,3]
print(findSub(s, nums))

1456：定长字串中 元音字母 的最大数目
输入：s = 'abciiidef' k = 3（子串定长为3）
输出：3
解释：子字符串 'iii' 包含 3 个元音字母

def countSub(s, k):
    if s == None or len(s) == 0 or len(s) < k:
        return 0
    
    # 元音字母哈希
    hashset = {'a', 'e', 'i', 'o', 'u'}
    res = 0
    count = 0
    for i in range(k):          # 窗口为 k
        if s[i] in hashset:
            count += 1
        res = max(res, count)
    for i in range(k, len(s)):
        if s[i-k] in hashset:   # 窗口右移
            count -= 1
        if s[i] in hashset:
            count += 1
        res = max(res, count)

    return res

s = 'abciiidef'   
k = 3
print(countSub(s, k))