算法|数组——滑动窗口
引入
给定一个含有 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
解法
暴力解法
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = Integer.MAX_VALUE;
for(int i = 0; i < nums.length; i++){
int sum = 0;
for(int j = i; j < nums.length; j++){
sum += nums[j];
if(sum >= target){
result = Math.min(result,j - i + 1);
break;
}
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
这种做法可以很容易想到,可是谁想到它…
超时了哈哈😓😓😓😓😓😓😓😓
那么下面我们看看另外一种思路。
滑动窗口
先看示例代码:
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int result = Integer.MAX_VALUE;
int i = 0;
int sum = 0;
int length = 0;
for(int j = 0; j < nums.length; j++){
sum += nums[j];
while(sum >= target){
length = j - i + 1;
result = Math.min(result,length);
sum -= nums[i++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
下面见分析:
还不错吧😊😊😊😼
文章来源:https://www.toymoban.com/news/detail-659090.html
至此先不更个1-2天,哥们要考科四,现在一题都没看,再不看就寄了😥😥😥😥文章来源地址https://www.toymoban.com/news/detail-659090.html
到了这里,关于【算法|数组】滑动窗口的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!