力扣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 <= 109
-
1 <= nums.length <= 105
-
1 <= nums[i] <= 105
暴力解法:
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int ans=Integer.MAX_VALUE;//最终结果
int res=0;//每次遍历得到的值
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){
res=j-i+1;
if(res<ans){
ans=res;
}
break;
}
}
}
return ans == Integer.MAX_VALUE? 0 : ans;
// if(ans!=Integer.MAX_VALUE){
// return ans;
// }else{
// return 0;
// }
}
}
超时↑
滑动窗口(双指针):
所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。
在暴力解法中,一个for循环为滑动窗口的起始位置,一个for循环为滑动窗口的终止位置
那么滑动窗口如何用一个for循环来完成这个操作呢?
首先要思考如果用一个for循环,那么应该表示滑动窗口的起始位置,还是终止位置。
如果只用一个for循环来表示滑动窗口的起始位置,那么如何遍历剩下的终止位置?此时难免再次陷入 暴力解法的怪圈。
只用一个for循环,那么这个循环的索引,一定是表示滑动窗口的终止位置
class Solution {
public int minSubArrayLen(int target, int[] nums) {
//滑动窗口(双指针)
int l=0,r=0,ans=Integer.MAX_VALUE,sum=0,res=0;
for(r=0;r<nums.length;r++){
sum+=nums[r];
while(sum>=target){
res=r-l+1;
if(res<ans){
ans=res;
}
sum-=nums[l];
l++;
}
}
return ans == Integer.MAX_VALUE? 0 : ans;
}
}
原文地址:https://blog.csdn.net/m0_74931837/article/details/142711073
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!