每日OJ题_算法_滑动窗口①_介绍+力扣209. 长度最小的子数组

目录

力扣209. 长度最小的子数组

解析代码

---

滑动窗口算法介绍

滑动窗口算法（Sliding Window Algorithm）是一种常见的算法技巧，用于解决一些数组或字符串相关的问题。滑动窗口算法的本质是同向双指针，双指针算法已经在前面博客讲过了，所谓滑动窗口，顾名思义可以理解成是一个会滑动的窗口，每次记录下窗口的状态，再找出符合条件的适合的窗口。它可以将双层嵌套的循环问题，转换为单层遍历的循环问题。使用两个指针一左一右构成一个窗口，就可以将二维循环的问题转化成一维循环一次遍历，相当于通过旧有的计算结果对搜索空间进行剪枝，使时间复杂度从O（N^2）降低至O（N），比如经典字符串查找算法Rabin-Karp 指纹字符串查找算法，它本质上也使用了滑动窗口的思想，通过公式推导降低窗口滑动时计算子串哈希值的复杂度。

算法原理：

1. 窗口大小：滑动窗口算法通过设定一个窗口的大小来解决问题。窗口通常是一个连续的子数组或子字符串。
2. 初始化窗口：初始化窗口的起始位置，并根据问题需求设定窗口的大小。
3. 移动窗口：通过移动窗口的起始位置，不断调整窗口的大小和位置，以找到满足问题条件的解。
4. 更新解：根据窗口的移动和调整，更新问题的解，并记录或返回所需的结果。

应用场景：

• 最小/最大子数组/子字符串：寻找给定数组或字符串中满足特定条件的最小或最大的子数组或子字符串。
• 字符串匹配：在一个字符串中寻找另一个字符串的出现或满足特定条件的子串。
• 滑动窗口和哈希表结合：通过使用哈希表来优化滑动窗口算法，提高效率。
• 优化窗口大小：根据问题的特性，调整窗口大小以寻找最佳解。

算法通常步骤：

1. 初始化窗口的起始位置和结束位置，使其满足问题的要求。
2. 进入循环，不断移动窗口的起始位置和结束位置，直到窗口滑动到数组或字符串的末尾。
3. 在每一次循环中，检查窗口内的元素是否满足问题的要求。如果满足条件，则更新解或执行其他操作。如果不满足条件，则继续移动窗口。
4. 在移动窗口时，要更新窗口内的元素和相应的数据结构，以确保窗口的正确性。
5. 重复步骤2到步骤4，直到遍历完整个数组或字符串，返回解或所需的结果。

---

力扣209. 长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode）

难度 中等

给定一个含有 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 <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

进阶：

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

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
 
    }
};

---

解析代码

首先想到的是暴力枚举，定义两个指针和一个变量，可以做到时间为O（N^2）。

由于此问题分析的对象是一段连续的区间，因此可以考虑滑动窗口的思想来解决这道题。

本题为变长的滑动窗口，其窗口大小由target决定（窗口总和大于等于target），所以定义一个变量（窗口内总和），小于target右指针右移，大于target左指针右移，等于记录更新窗口大小即可。

i 位置开始，窗口内所有元素的和小于 target让滑动窗口满足：(那么当窗口内元素之和第一次大于等于目标值的时候，就是 i 位置开始，满足条件的最小长度)
做法：将右端元素划入窗口中，统计出此时窗口内元素的和：如果窗口内元素之和大于等于 target : 更新结果，并且将左端元素划出去的同时继续判断是否满足条件并更新结果(因为左端元素可能很小，划出去之后依旧满足条件，如果窗口内元素之和不满足条件：right++ ，另下一个元素进入窗口。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // 时间：O（N）
        int n = nums.size(), ret = n + 1; // 返回值不可能超过数组长度
        int sum = 0, left = 0, right = 0;
        while(right < n)
        {
            sum += nums[right]; // 进窗口
            while(sum >= target) // 判断
            {
                ret = min(ret, right - left + 1); // 更新结果
                sum -= nums[left++]; // 出窗口 然后left++
            }
            ++right; // 判断不符合了
        }
        return ret == n + 1 ? 0 : ret;
    }
};

为什么滑动窗口可以解决问题，并且时间复杂度更低?

本质是利用单调性规避了很多不必要的枚举。
这个窗口寻找的是：以当前窗口最左侧元素 （记为 left）为基准，符合条件的情况。也就是在这道题中，从 left 开始，满足区间和 sum >= target 时的最右侧 （记为right)）能到哪里。
我们既然已经找到从 left 开始的最优的区间，那么就可以大胆舍去  left 。但是如果继续像暴力枚举，重新开始统计第二个元素 后的和，势必会有大量重复的计算 （因为我们在求第一段区间的时候，已经算出很多元素的和了，这些和是可以在计算下次区间和的时候用上的）。
此时，rigth 的作用就体现出来了，我们只需将 left 这个值从 sum 中剔除。从right 这个元素开始，往后找满足的区间（此时 right 也有可能是满足的，因为 left 可能很小。 sum 剔除掉 left 之后，依旧满足大于等于target ）。这样就能省掉大量重复的计算。

这样不仅能解决问题，而且效率也会大大提升时间复杂度：虽然代码是两层循环，但是 left 指针和 right 指针都是不回退的，两者最多都往后移动 N 次。因此时间复杂度是 0(N)。