【面试高频算法解析】算法练习4 滑动窗口

前言

本专栏旨在通过分类学习算法，使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目，帮助您深度理解每种算法，避免出现刷了很多算法题，还是一知半解的状态

---

专栏导航

1. 二分查找
2. 回溯（Backtracking）
3. 双指针
4. 滑动窗口
5. 深度优先搜索
6. 广度优先搜索
7. 贪心算法
8. 单调队列
9. 堆（Heap）

---

算法解析

滑动窗口是一种常用的算法技术，主要用于处理数组或字符串的连续子元素问题。这种技术可以让我们在不必要的重复计算中节省时间，特别是在涉及到连续子数组/子字符串的最优化问题时，如计算最大/最小的子数组和或者找到包含或不包含某些元素的最短/最长子数组。

滑动窗口算法通常定义两个指针（索引），这两个指针表示窗口的起始和结束位置。窗口可以是固定大小，也可以是动态变化的。算法的基本步骤如下：

1. 初始化：将两个指针（通常称为 left 和 right）都置于数组的起始位置。

2. 扩展窗口：将 right 指针向右移动以包含更多的元素直到满足特定条件。

3. 收缩窗口：一旦满足了问题的约束条件（例如窗口内的元素总和达到了目标值），开始移动 left 指针以尝试找到更小的窗口或为下一个可能的解腾出空间。

4. 记录结果：在窗口移动的过程中，根据问题的需求记录所需的结果，比如最大/最小的子数组和或者最短/最长的满足条件的子数组长度。

5. 重复步骤2和3：继续移动 right 和 left 指针，直到 right 指针到达数组的末尾。

滑动窗口技术广泛应用于解决复杂度为 O(n) 的问题，因为它可以确保每个元素最多被访问两次（由 left 和 right 指针各一次），从而避免了 O(n^2) 的暴力解法。

下面是一个使用滑动窗口解决“最大子数组和”问题的示例：

def max_subarray_sum(nums, k):
    max_sum = 0
    window_sum = 0
    left = 0

    for right in range(len(nums)):
        # 扩展窗口
        window_sum += nums[right]

        # 窗口大小达到k时，开始滑动
        if right >= k - 1:
            max_sum = max(max_sum, window_sum)
            # 收缩窗口
            window_sum -= nums[left]
            left += 1

    return max_sum

在这个例子中，我们要找到大小为 k 的最大子数组和。我们维护一个当前窗口的总和 window_sum，每次右指针向右移动时，都会增加新元素到 window_sum。当窗口大小达到 k 时，我们检查是否可以更新最大子数组和 max_sum，然后移动左指针收缩窗口并从 window_sum 中减掉左边的元素。这样我们就能在 O(n) 的时间复杂度内解决问题。

---

实战练习

长度最小的子数组

给定一个含有 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

提示：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶：
如果你已经实现 O(n²) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

官方题解

---

无重复字符的最长子串

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

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

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

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

示例 4:
输入: s = “”
输出: 0

提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

官方题解

---

找到K个最接近的元素

给定一个 排序好 的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

整数 a 比整数 b 更接近 x 需要满足：
|a - x| < |b - x| 或者
|a - x| == |b - x| 且 a < b

示例 1：
输入：arr = [1,2,3,4,5], k = 4, x = 3
输出：[1,2,3,4]

示例 2：
输入：arr = [1,2,3,4,5], k = 4, x = -1
输出：[1,2,3,4]

提示：
1 <= k <= arr.length
1 <= arr.length <= 104
arr 按 升序 排列
-104 <= arr[i], x <= 104

官方题解