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

目录

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

解析代码

力扣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) {

    }
};

解析代码

由于此问题分析的对象是一段连续的区间]，因此可以考虑T滑动窗口]的思想来解决这道题i 位置开始，窗口内所有元素的和小于 target让滑动窗口满足：(那么当窗口内元素之和第一次大于等于目标值的时候，就是 i 位置开始，满足条件的最小长度)
做法：将右端元素划入窗口中，统计出此时窗口内元素的和：如果窗口内元素之和大于等于 target : 更新结果，并且将左端元素划出去的同时继续判断是否满足条件并更新结果(因为左端元素可能很小，划出去之后依旧满足条件，如果窗口内元素之和不满足条件：right++ ，另下一个元素进入窗口。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size(), ret = n + 1, sum = 0, left = 0, right = 0;
        while(right < n)
        {
            sum += nums[right]; // 进窗口
            while(sum >= target) // 判断
            {
                ret = min(ret, right - left + 1); // 更新结果
                sum -= nums[left++]; // 出窗口
            }
            ++right;
        }
        return ret == n + 1 ? 0 : ret;
    }
};

为什么滑动窗口可以解决问题，并且时间复杂度更低?
这个窗口寻找的是：以当前窗口最左侧元素 (记为 left1)为基准，符合条件的情况。也
就是在这道题中，从 left1 开始，满足区间和 sum >= target 时的最右侧 (记为right1 ) 能到哪里。
我们既然已经找到从 left1 开始的最优的区间，那么就可以大胆舍去 ?eft1 。但是如果继续像方法一一样，重新开始统计第二个元素 (left2) 后的和，势必会有大量重复的计算 (因为我们在求第一段区间的时候，已经算出很多元素的和了，这些和是可以在计算下次区间和的时候用上的)。
此时，rigth1 的作用就体现出来了，我们只需将 left1 这个值从 sum 中剔除。从right1 这个元素开始，往后找满足 ?eft2 元素的区间(此时 right1 也有可能是满足的，因为 left1 可能很小。 sum 剔除掉 Left1 之后，依旧满足大于等于target )。这样我们就能省掉大量重复的计算。
这样我们不仅能解决问题，而且效率也会大大提升时间复杂度:虽然代码是两层循环，但是我们的 eft 指针和ight 指针都是不回退的，两者最多都往后移动 n 次。因此时间复杂度是 0(N)。