Leetcode (滑动窗口基础)209.长度最小的子数组

前言

如果你是第一次做滑动窗口，本题是个很好的例子

题目描述

209.长度最小的子数组

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

解题方式

暴力

第一眼看到此题，你可能会尝试暴力，则枚举$i$和$j$，然后判断子数组里的元素是否$>=target$

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        ans = 10 ** 9 # 初始化一个无穷大的答案
        for i in range(0,len(nums)):
            o = 0 #子数组的元素和
            for j in range(i,len(nums)):
                o+=nums[j] # 循环一次加一个
                if o >= target: # 判断
                    ans = min(ans,j-i+1) # 更新答案 注意 这里+1是因为自己也要算进去
        if ans == 10**9: return 0 # 如果没有答案就返回0
        return ans

时间复杂度:$O(n^2)$

空间复杂度:$O(1)$

但是很遗憾，暴力超时了，我们看回提示中的$1<=nums.length<=10^5$，就是数组范围最坏情况是$10^5$个元素，这样双层循环肯定会超时

因此我们需要把$O(n^2)$的时间复杂度优化到$O(n)$

滑动窗口

• Q:什么情况下用滑动窗口
• A:像这样的子数组问题，或者连续区间问题，都可以用滑动窗口

滑动窗口本质就是定义左右边界，然后枚举右边界，维护左边界，并在满足条件下更新答案

首先定义$i$和$j$,$i$为左边界,$j$为右边界，再定义一个无穷大的答案$ans$一般为$10^9$,以及一个$t$ $t$代表子$nums$里的元素和,然后开始思考如何维护左边界，如何更新答案

先回答第一个问题

• 当$t>=target$时，我们去缩小左边界，查找有没有更小长度的子数组，并更新$ans$

第二个问题

• 当$i$在缩小的时候，判断$t>=target$,更新当前答案为$j-i+1$，注：当出现只有一个元素的时候 要加上自己 所以要+1

明白这些问题后，我们就开始写代码了

首先定义$i$,$j$,$ans$,$t$

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        i=0;j=0;ans=10**9;t=0

写一个循环枚举右边界$j$

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        i=0;j=0;ans=10**9;t=0
        while j < len(nums):
            j+=1

开始维护子数组的元素，并加上维护$i$

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        i=0;j=0;ans=10**9;t=0
        while j < len(nums):
            t+=nums[j] # 添加子数组元素
            while i <= j and t >= target:
                ## 保持左右边界不相反 而且 t>=target
                if t >= target:
                    ans = min(ans,j-i+1) # 更新答案
                t-=nums[i] # 删除子数组元素
                i+=1
            j+=1 # 枚举右边界
        if ans == 10 ** 9: return 0 # 如果答案还是无穷大 说明没有符合的子数组
        return ans

这样我们就遍历了一次数组解决了问题 可以通过本题了

示例代码

Python

# 时间复杂度:O(n)
# 空间复杂度:O(1)
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        i=0;j=0;ans=10**9;t=0
        while j < len(nums):
            t+=nums[j]
            while i <= j and t >= target:
                if t >= target:
                    ans = min(ans,j-i+1)
                t-=nums[i]
                i+=1
            j+=1
        if ans == 10 ** 9: return 0
        return ans

C++

// 时间复杂度:O(n)
// 空间复杂度:O(1)
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i = 0;
        int j = 0;
        int t = 0;
        int ans = 100000000;
        while(j<nums.size()){
            t+=nums[j];
            while(i<=j&&t>=target){
                ans=min(ans,j-i+1);
                t-=nums[i];
                i++;
            }
            j++;
        }
        if(ans==100000000){return 0;}
        return ans;
    }
};