算法-滑动窗口思想

def sliding_window(nums, k):  # k可能是固定窗口大小或其他条件
    # 初始化窗口边界和结果
    left = 0
    result = 0  # 根据题目调整（可能是最大值、最小值、计数等）
    window = {}  # 用于记录窗口内元素状态的数据结构

    # 右指针遍历整个数组/字符串
    for right in range(len(nums)):
        # 1. 扩大窗口，将右指针元素加入窗口
        window[nums[right]] = window.get(nums[right], 0) + 1
        
        # 2. 根据条件收缩窗口（while循环）
        while 窗口不满足条件:
            # 移除左指针元素
            window[nums[left]] -= 1
            if window[nums[left]] == 0:
                del window[nums[left]]
            left += 1
        
        # 3. 更新结果
        result = max(result, right - left + 1)  # 或其他更新逻辑
    
    return result

def fixed_window(nums, k):
    # 初始化
    left = 0
    window = {}  # 或其他数据结构
    result = 0  # 或其他初始值
    
    for right in range(len(nums)):
        # 加入窗口
        window[nums[right]] = window.get(nums[right], 0) + 1
        
        # 当窗口大小超过k时，移除左侧元素
        if right - left + 1 > k:
            window[nums[left]] -= 1
            if window[nums[left]] == 0:
                del window[nums[left]]
            left += 1
        
        # 当窗口大小等于k时，更新结果
        if right - left + 1 == k:
            # 更新result
            pass
    
    return result

def variable_window(nums, condition):
    # 初始化
    left = 0
    window = {}  # 或其他数据结构
    result = 0  # 或其他初始值
    
    for right in range(len(nums)):
        # 加入窗口
        window[nums[right]] = window.get(nums[right], 0) + 1
        
        # 根据条件收缩窗口
        while 不满足条件:
            window[nums[left]] -= 1
            if window[nums[left]] == 0:
                del window[nums[left]]
            left += 1
        
        # 更新结果
        result = max/min(result, right - left + 1)  # 或其他更新逻辑
    
    return result

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()  # 用集合记录窗口中的字符
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        # 如果出现重复字符，收缩窗口
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        
        # 加入新字符
        char_set.add(s[right])
        
        # 更新最大长度
        max_length = max(max_length, right - left + 1)
    
    return max_length

def maxSubArrayLen(nums: List[int], k: int) -> int:
    prefix_sum = {0: -1}  # 前缀和 -> 索引
    max_len = 0
    curr_sum = 0
    
    for i, num in enumerate(nums):
        curr_sum += num
        
        # 如果curr_sum - k存在于prefix_sum中，则找到了一个和为k的子数组
        if curr_sum - k in prefix_sum:
            max_len = max(max_len, i - prefix_sum[curr_sum - k])
        
        # 只保存第一次出现的前缀和，以获得最长子数组
        if curr_sum not in prefix_sum:
            prefix_sum[curr_sum] = i
    
    return max_len

def minWindow(s: str, t: str) -> str:
    if not t or not s:
        return ""
    
    # 统计t中每个字符的出现次数
    dict_t = {}
    for char in t:
        dict_t[char] = dict_t.get(char, 0) + 1
    
    # 所需字符数量
    required = len(dict_t)
    
    # 窗口初始化
    left, right = 0, 0
    formed = 0  # 已满足条件的字符种类数
    window_counts = {}
    
    # 结果初始化
    min_len = float("inf")
    result = ""
    
    while right < len(s):
        # 扩大窗口
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        # 检查字符是否满足条件
        if char in dict_t and window_counts[char] == dict_t[char]:
            formed += 1
        
        # 尝试收缩窗口
        while left <= right and formed == required:
            char = s[left]
            
            # 更新结果
            if right - left + 1 < min_len:
                min_len = right - left + 1
                result = s[left:right + 1]
            
            # 收缩窗口
            window_counts[char] -= 1
            if char in dict_t and window_counts[char] < dict_t[char]:
                formed -= 1
            
            left += 1
        
        right += 1
    
    return result