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

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

# 变长度的滑动窗口
import collections
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        left = 0
        right = 0
        count = 0    # 用来统计相同字符
        start = 0    # 数组的开始位置
        size = len(s) + 1
        
        # 创建目标字符串t 的字典
        t_dict = collections.defaultdict(int)
        for i in t:
            t_dict[i] += 1
        # 创建滑动窗口window 的字典
        window = collections.defaultdict(int)
        
        while right < len(s):
            insert_char = s[right]
            right += 1
            # 窗口字典更新
            if insert_char in t_dict:
                window[insert_char] += 1
                if window[insert_char] == t_dict[insert_char]:
                    count += 1
            
            # 窗口左边界右移
            while count == len(t_dict):
                # 移动带来的数据更新
                if right - left < size:
                    start = left
                    size = right - left
                remove_char = s[left]
                left += 1

                if remove_char in t_dict:
                    if window[remove_char] == t_dict[remove_char]:
                        count -= 1
                    window[remove_char] -= 1
        if size == len(s) + 1:
            return ''
        return s[start: start+size]

1658. 将 x 减到 0 的最小操作数

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

输入：nums = [5,6,7,8,9], x = 4
输出：-1

# 滑动窗口
# 将 x 减到 0 的最小操作数可以转换为求和等于 sum(nums) - x 的最长连续子数组长度。
# 可以维护一个区间和为 sum(nums) - x 的滑动窗口，求出最长的窗口长度
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        target = sum(nums) - x
        # 特殊情况
        if target < 0:
            return -1
        if target == 0:
            return len(nums)

        left = 0
        right = 0
        window_sum = 0
        maxlen = float('-inf')

        while right < len(nums):
            window_sum += nums[right]
            # 窗口左移
            while window_sum > target:
                window_sum -= nums[left]
                left += 1 
            # 维护窗口的最大长度
            if window_sum == target:
                maxlen = max(maxlen, right-left+1)
            right += 1
        if maxlen == float('-inf'):
            return -1 
        else:
            return len(nums) - maxlen