本文主要是介绍[优选算法]------滑动窗⼝——209. 长度最小的子数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
1.题目
1.解法⼀(暴⼒求解)(会超时):
2.解法⼆(滑动窗⼝):
1.算法思路:
2.手撕图解
3.代码实现
1.C++
2.C语言
1.题目
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
1.解法⼀(暴⼒求解)(会超时):
算法思路:
「从前往后」枚举数组中的任意⼀个元素,把它当成起始位置。然后从这个「起始位置」开始,然
后寻找⼀段最短的区间,使得这段区间的和「⼤于等于」⽬标值。
将所有元素作为起始位置所得的结果中,找到「最⼩值」即可。
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {// 记录结果int ret = INT_MAX;int n = nums.size();// 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]// 由于是取到最⼩,因此枚举的过程中要尽量让数组的⻓度最⼩// 枚举开始位置for (int start = 0; start < n; start++) {int sum = 0; // 记录从这个位置开始的连续数组的和// 寻找结束位置for (int end = start; end < n; end++) {sum += nums[end]; // 将当前位置加上if (sum >= target) // 当这段区间内的和满⾜条件时{// 更新结果,start 开头的最短区间已经找到ret = min(ret, end - start + 1);break;}}}// 返回最后结果return ret == INT_MAX ? 0 : ret;}
};
2.解法⼆(滑动窗⼝):
1.算法思路:
由于此问题分析的对象是「⼀段连续的区间」,因此可以考虑「滑动窗⼝」的思想来解决这道题。
让滑动窗⼝满⾜:从 i 位置开始,窗⼝内所有元素的和⼩于target(那么当窗⼝内元素之和
第⼀次⼤于等于⽬标值的时候,就是 i 位置开始,满⾜条件的最⼩⻓度)。
做法:将右端元素划⼊窗⼝中,统计出此时窗⼝内元素的和:
▪ 如果窗⼝内元素之和⼤于等于 target :更新结果,并且将左端元素划出去的同时继续判
断是否满⾜条件并更新结果(因为左端元素可能很⼩,划出去之后依旧满⾜条件)
▪ 如果窗⼝内元素之和不满⾜条件: right++ ,另下⼀个元素进⼊窗⼝。
相信科学(这也是很多题解以及帖⼦没告诉你的事情:只给你说怎么做,没给你解释为什么这么
做):
为何滑动窗⼝可以解决问题,并且时间复杂度更低
▪ 这个窗⼝寻找的是:以当前窗⼝最左侧元素(记为 left1 )为基准,符合条件的情况。也
就是在这道题中,从 left1 开始,满⾜区间和 sum >= target 时的最右侧(记为right1 )能到哪⾥。
▪ 我们既然已经找到从 left1 开始的最优的区间,那么就可以⼤胆舍去 left1 。但是如
果继续像⽅法⼀⼀样,重新开始统计第⼆个元素( left2 )往后的和,势必会有⼤量重复
的计算(因为我们在求第⼀段区间的时候,已经算出很多元素的和了,这些和是可以在计算
下次区间和的时候⽤上的)。
▪ 此时, rigth1 的作⽤就体现出来了,我们只需将 left1 这个值从 sum 中剔除。从right1 这个元素开始,往后找满⾜eft2 元素的区间(此时right1也有可能是满⾜的,因为 left1 可能很⼩。 sum 剔除掉left1 之后,依旧满⾜⼤于等于target )。这样我们就能省掉⼤量重复的计算。
▪ 这样我们不仅能解决问题,⽽且效率也会⼤⼤提升。
时间复杂度:虽然代码是两层循环,但是我们的 left 指针和right 指针都是不回退的,两者
最多都往后移动 n 次。因此时间复杂度是O(N) 。
2.手撕图解
3.代码实现
INT_MAX是C语言中的一个宏定义,表示整型数据类型int的最大值。在32位系统中,它的值为2147483647;在64位系统中,它的值为9223372036854775807。这个值可以用来进行数据类型转换、判断数据是否越界等操作。
1.C++
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size(), sum = 0, len = INT_MAX;for (int left = 0, right = 0; right < n; right++) {sum += nums[right]; // 进窗⼝while (sum >= target) // 判断{len = min(len, right - left + 1); // 更新结果sum -= nums[left++]; // 出窗⼝}}return len == INT_MAX ? 0 : len;}
};
2.C语言
int minSubArrayLen(int target, int* nums, int numsSize)
{int sum = 0, len = INT_MAX;for (int left = 0, right = 0; right < numsSize; right++) {sum += nums[right]; // 进窗⼝while (sum >= target) // 判断{len = len < right - left + 1 ? len : right - left + 1; // 更新结果sum -= nums[left++]; // 出窗⼝}}return len == INT_MAX ? 0 : len;
}
这篇关于[优选算法]------滑动窗⼝——209. 长度最小的子数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!