447_滑动窗口面试题¶

# 可变窗口模板
left = 0
for right in range(len(s)):
    # 1. 将 right 纳入窗口，更新窗口状态
    window.update(s[right])

    # 2. 当窗口不满足条件时，收缩左边界
    while window_is_invalid():
        window.remove(s[left])
        left += 1

    # 3. 更新结果（此时窗口合法）
    ans = max(ans, right - left + 1)

def length_of_longest_substring(s: str) -> int:
    """
    可变窗口：右边界不断扩展，遇到重复字符收缩左边界
    用集合记录窗口内的字符
    """
    char_set = set()                       # 窗口内的字符集合
    left = 0                               # 窗口左边界
    max_len = 0                            # 最长子串长度

    for right in range(len(s)):
        # 如果 right 指向的字符已在窗口中，收缩左边界直到无重复
        while s[right] in char_set:
            char_set.remove(s[left])       # 移除左边界字符
            left += 1                      # 左边界右移

        char_set.add(s[right])             # 将新字符加入窗口
        max_len = max(max_len, right - left + 1)  # 更新最大长度

    return max_len

# 优化版：用字典记录字符最后出现的位置，直接跳跃左边界
def length_of_longest_substring_v2(s: str) -> int:
    char_pos = {}                          # {字符: 最后出现的位置}
    left = 0
    max_len = 0

    for right, c in enumerate(s):
        # 如果字符已见且在窗口内，直接跳跃左边界
        if c in char_pos and char_pos[c] >= left:
            left = char_pos[c] + 1         # 跳到重复字符的下一位
        char_pos[c] = right                # 更新字符位置
        max_len = max(max_len, right - left + 1)

    return max_len

# 测试
print(length_of_longest_substring("abcabcbb"))  # 3（"abc"）
print(length_of_longest_substring("bbbbb"))     # 1（"b"）
print(length_of_longest_substring("pwwkew"))    # 3（"wke"）

from collections import Counter

def min_window(s: str, t: str) -> str:
    """
    可变窗口：右边界扩展，窗口覆盖t后收缩左边界找最小
    用 Counter 记录窗口状态和目标状态的差距
    """
    if not t or not s:
        return ""

    need = Counter(t)                      # 需要的字符及数量
    window = Counter()                     # 当前窗口的字符及数量
    have = 0                               # 窗口中已满足的字符种数
    required = len(need)                   # 需要满足的字符种数

    left = 0
    min_len = float('inf')
    result = ""

    for right in range(len(s)):
        c = s[right]
        window[c] += 1                     # 右边界字符纳入窗口

        # 如果当前字符满足了其在 t 中的需求
        if c in need and window[c] == need[c]:
            have += 1                      # 满足的种数+1

        # 当窗口已覆盖 t 的所有字符时，尝试收缩
        while have == required:
            if right - left + 1 < min_len: # 更新最小窗口
                min_len = right - left + 1
                result = s[left:right + 1]

            # 收缩左边界
            left_c = s[left]
            window[left_c] -= 1
            if left_c in need and window[left_c] < need[left_c]:
                have -= 1                  # 满足的种数-1
            left += 1

    return result

# 测试
print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"
print(min_window("a", "a"))                # "a"
print(min_window("a", "aa"))               # ""（s中没有两个a）

def min_sub_array_len(target: int, nums) -> int:
    """
    可变窗口：右边界扩展，当窗口和>=target时收缩左边界找最小
    """
    left = 0
    window_sum = 0                         # 窗口内元素的和
    min_len = float('inf')

    for right in range(len(nums)):
        window_sum += nums[right]          # 纳入右边界

        # 满足条件时收缩左边界
        while window_sum >= target:
            min_len = min(min_len, right - left + 1)  # 更新最小长度
            window_sum -= nums[left]       # 移除左边界
            left += 1                      # 左边界右移

    return min_len if min_len != float('inf') else 0

# 测试
print(min_sub_array_len(7, [2,3,1,2,4,3]))  # 2（子数组[4,3]）
print(min_sub_array_len(4, [1,4,4]))        # 1（子数组[4]）
print(min_sub_array_len(11, [1,1,1,1,1]))   # 0（不存在）

# 固定大小窗口（大小为k）
window_sum = sum(nums[:k])
max_sum = window_sum
for i in range(k, len(nums)):
    window_sum += nums[i] - nums[i-k]     # 右边进，左边出
    max_sum = max(max_sum, window_sum)

# 可变窗口模板
left = 0
state = {}                                # 窗口状态
for right in range(len(s)):
    state.update(s[right])                # 纳入右边界
    while not valid(state):               # 不合法时收缩
        state.remove(s[left])
        left += 1
    ans = update(ans, right - left + 1)   # 更新结果