分享几道和「滑动窗口」有关的算法面试题

作为一个算法面试题，滑动窗口通常用于解决字符串相关的问题。下面将为大家介绍两道和「滑动窗口」有关的算法面试题，分别是「最小覆盖子串」和「长度最小的子数组」，希望能够对大家有所帮助。

最小覆盖子串

该题中给定两个字符串 S 和 T，要求在字符串 S 中找到最小的覆盖子串，使得这个子串中包含了字符串 T 中的所有字符。

为了方便解题，我们可以使用两个哈希表来记录字符串 T 中每个字符出现的次数和 S 中每个字符出现的次数，同时维护两个指针 left 和 right，分别表示窗口的左边界和右边界。在移动右边界的过程中，我们可以判断当前窗口是否包含了字符串 T 中的所有字符，如果是则尝试移动左边界，并更新最小窗口长度。

具体的代码实现如下：

def minWindow(s: str, t: str) -> str:
    if not s or not t:
        return ""

    left, right = 0, 0
    target = {}
    windows = {}
    for c in t:
        target[c] = target.get(c, 0) + 1
    match = 0
    min_len, start = float("inf"), 0

    while right < len(s):
        c1 = s[right]
        if c1 in target:
            windows[c1] = windows.get(c1, 0) + 1
            if windows[c1] == target[c1]:
                match += 1

        right += 1

        while match == len(target):
            if right - left < min_len:
                min_len = right - left
                start = left

            c2 = s[left]
            if c2 in target:
                windows[c2] -= 1
                if windows[c2] < target[c2]:
                    match -= 1

            left += 1

    return "" if min_len == float("inf") else s[start:start+min_len]

长度最小的子数组

该题中给定一个整数数组和一个目标值 target，要求在数组中找到一个连续的子数组，使得这个子数组的和大于等于目标值 target，且长度最小。

我们可以使用双指针的方法，维护一个指针 left 和一个指针 right，表示当前子数组的左右边界。在移动右指针的过程中，累加当前子数组的和，并判断是否大于等于目标值 target。如果是，尝试移动左指针，并更新最短子数组长度。具体的代码实现如下：

def minSubArrayLen(s: int, nums: List[int]) -> int:
    if not nums:
        return 0

    left, right = 0, 0
    curr_sum = 0
    min_len = float("inf")

    while right < len(nums):
        curr_sum += nums[right]
        right += 1

        while curr_sum >= s:
            min_len = min(min_len, right - left)
            curr_sum -= nums[left]
            left += 1

    return 0 if min_len == float("inf") else min_len

通过以上两个示例，我们可以看到滑动窗口算法在解决字符串和数组相关的问题时具有很高的效率和可行性，也是面试中经常会遇到的算法之一。