「Leetcode」滑动窗口—长度最小的子数组

2023-12-13 19:56:24
在这里插入图片描述


📄题目

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 ≤ t a r g e t ≥ 1 0 9 1 \le target \ge 10^9 1target109
  • 1 ≤ n u m s . l e n g t h ≥ 1 0 5 1 \le nums.length \ge 10^5 1nums.length105
  • 1 ≤ n u m s [ i ] ≥ 1 0 5 1 \le nums[i] \ge 10^5 1nums[i]105

??题目解析 & 思路

题目要求我们在数组中寻找和为target的最小子数组,我们可以先去想出暴力解法,然后再推算出滑动窗口的解法。

暴力法
我们需要找到最短的连续数组,那么最简单的方式就是用两个for循环去遍历数组累加数值,只要数值 ≥ t a r g e t \ge target target 就更新最小长度的状态。

在这里插入图片描述

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ret = INT_MAX;
        for(int left = 0; left < n; ++left)
        {
            int sum = 0;
            for(int right = left; right < n; ++right)	
            {
                sum += nums[right];						//累加数据
                if(sum >= target)
                {
                    ret = min(ret, right - left + 1);	//更新状态
                    break;								//已经找到了最小的长度,所以退出该层循环
                }
            }
        }
        
        return ret == INT_MAX ? 0 : ret;
    }
};

时间复杂度: O ( n 2 ) O(n^2) O(n2)
空间复杂度: O ( 1 ) O(1) O(1)

滑动窗口

滑动窗口的题目大抵都有一个固定的划分过程:

  1. ++right
  2. 进窗口
  3. 判断
    • 更新结果状态(根据题目不同,也可能在判断后更新状态)
    • 出窗口(++left)

我们从暴力法中不难发现,其实当我们更新最小子数组长度时, l e f t + 1 → r i g h t left+1\to right left+1right 的这段区间是重复遍历的,于是我们便可以使用滑动窗口来进行优化。当我们的 s u m ≥ t a r g e t sum \ge target sumtarget 时,同时更新 l e f t left left 的位置 与 最小子数组的长度,所谓的滑动窗口也是一种特殊的双指针类型,只不过两个指针的指向都是相同的方向。

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

        return ret == INT_MAX ? 0 : ret;	//返回结果
    }
};

时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)

📓总结

📜博客主页:主页
📫我的专栏:C++
📱我的github:github

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