[leetcode] 面试经典 150 题——篇3：滑动窗口

方法概述

滑动窗口是一种常用的算法技巧，特别适用于需要在数组或序列上找到满足某些条件的子数组（或子串）的问题。它通过维护一个动态大小的“窗口”来遍历整个序列，并根据问题的要求调整这个窗口的大小和位置，从而高效地解决问题。以下是滑动窗口的基本原理：

基本原理

• 定义窗口：窗口通常由**两个指针（也称为边界）定义，这两个指针可以指向数组中的任意两个元素，形成一个范围。窗口内的元素是当前正在处理的数据集。
• 扩展窗口：通过移动右指针（通常是向右），逐步增加窗口的大小，将更多的元素包含进窗口内。在这个过程中，可以根据需要更新窗口内的状态（例如，总和、乘积等）。
• 收缩窗口：当窗口满足某个条件时（比如窗口内的元素总和超过了目标值），可以通过移动左指针来缩小窗口，移除一些不再需要的元素。这样可以在保持窗口内满足条件的同时，尝试找到更优解（如最小长度的子数组）。
• 重复上述过程：直到右指针遍历完整个数组或序列。在此过程中，不断根据题目要求更新最优解。

适用场景

滑动窗口技术非常适合于以下几类问题：

• 寻找满足某些条件的连续子数组或子串。
• 需要在序列中寻找最大/最小的连续部分，比如最大和子数组、最小和子数组长度等。
• 涉及到固定大小或可变大小的窗口操作，比如限制窗口内的唯一字符数、元素之和等。

示例说明

以寻找和大于等于给定目标值的最小长度子数组为例：

• 初始化窗口为数组的第一个元素，左右指针均指向数组的起始位置。
• 不断移动右指针扩大窗口，直到窗口内所有元素的和首次大于或等于目标值。
• 然后尝试移动左指针缩小窗口，同时检查是否仍然满足条件。如果满足，则记录当前窗口的长度并继续尝试缩小窗口；如果不满足，则停止缩小窗口，再次移动右指针。
• 重复上述步骤直到右指针到达数组末尾。

这种方法能有效地减少不必要的计算，时间复杂度通常为 O(n)，因为每个元素最多只会被访问两次（一次通过右指针，另一次通过左指针）。这使得滑动窗口成为解决这类问题的一种非常有效的方法。

1. [中等] 长度最小的子数组(leetcode 209题)

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于target 的长度最小的 子数组 [nums_l, nums_l+1, ..., nums_r-1, nums_r] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

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

解题思路

要解决这个问题，我们可以使用滑动窗口（双指针）的技术。这个方法可以有效地找到满足条件的最小子数组长度，而不需要对每个可能的子数组进行两两比较。下面是具体步骤：

• 初始化两个指针 left 和 right 来表示当前处理的子数组的左右边界，同时初始化一个变量来记录当前窗口内的元素总和以及另一个变量来保存满足条件的最小子数组长度。
• 移动右指针扩展窗口，并将新加入的元素加到当前窗口的总和中。
• 当窗口内元素的总和大于或等于目标值时，尝试收缩窗口（通过移动左指针），并在此过程中更新最小子数组长度。

重复上述过程直到遍历完整个数组。

python代码

def minSubArrayLen(target, nums):
    n = len(nums)
    left = 0
    current_sum = 0
    min_length = float('inf')  # 初始化最小长度为无穷大
    for right in range(n):
        current_sum += nums[right]  # 扩展窗口 
        while current_sum >= target:
            # 更新最小长度
            min_length = min(min_length, right - left + 1)
            # 收缩窗口
            current_sum -= nums[left]
            left += 1
    return min_length if min_length != float('inf') else 0
# 示例用法：
print(minSubArrayLen(7, [2,3,1,2,4,3]))  # 应输出 2

2. [中等] 无重复字符的最长子串(leetcode 5题)

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

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

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

解题思路

• 首先分辨子串和子序列的区别
  • 子串：s中出现的连续的一段
  • 子序列：s中出现的，不要求连续，但是相对位置关系不能变
• 求满足某些条件的子串问题，考虑用双指针方法求解。需要考虑以下问题：
  • 如何维护 "子串内容不重复"这个条件
  • 左右指针分别指向哪里
  • 左指针移动的条件是什么，右指针移动的条件是什么
  • 程序终止的条件是什么
• 考虑使用一个字典维护子串信息，key不可重复，根据元素有无在dict的key中判断元素是否出现过。左指针指向目标子串的左索引，右指针指向右索引；使用一个变量max_len表示最大子串；右指针取元素后，判断是否在dict中，不管是否存在，右指针都移动到下一个位置；如果右指针取元素后，不在dict中，则左指针不动，将元素保存到dict中，当右指针取到重复元素后，左指针移动到下一个位置，同样将元素保存到dict中；更新左右指针后，更新max_len值，max_len和(right - left + 1)相比取较大的值，当right遍历完毕s后，最后返回max_len

python代码

def length_of_longest_substring(s: str) -> int:
    char_map = {}  # 用来存储字符及其最新位置
    left = 0  # 窗口的左边界
    max_length = 0  # 记录最大长度
    for right in range(len(s)):
        if s[right] in char_map:  # 如果当前字符已经存在于char_map中，移动左指针
            left = max(left, char_map[s[right]] + 1) #更新左指针信息
        char_map[s[right]] = right  # 更新右指针信息
        max_length = max(max_length, right - left + 1)  # 更新最大长度
    return max_length

# 示例调用
s = "abcabdcbb"
print(length_of_longest_substring(s))  # 输出应该是3，因为"abc"是不含重复字符的最长子串