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

2024-01-07 21:10:45

前言

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


专栏导航

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

算法解析

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

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

  1. 初始化:将两个指针(通常称为 leftright)都置于数组的起始位置。

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

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

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

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

滑动窗口技术广泛应用于解决复杂度为 O(n) 的问题,因为它可以确保每个元素最多被访问两次(由 leftright 指针各一次),从而避免了 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 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 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(n2) 时间复杂度的解法, 请尝试设计一个 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

官方题解

文章来源:https://blog.csdn.net/sinat_41883985/article/details/135346682
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。