4
LeetCode.209 长度最小的子数组
source link: https://blog.51cto.com/u_15806469/6000382
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode.209 长度最小的子数组
精选 原创给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0
2.代码实现
1.暴力求解
int min=Integer.MAX_VALUE;
for(int i=0; i<nums.length; i++){
if(nums[i]>=target){
return 1;
}
int sum=nums[i];
for(int j=i+1; j<nums.length; j++){
sum=sum+nums[j];
if(sum>=target){
min = Math.min(min,j-i+1);
break;
}
}
}
return min==Integer.MAX_VALUE?0:min;
for(int i=0; i<nums.length; i++){
if(nums[i]>=target){
return 1;
}
int sum=nums[i];
for(int j=i+1; j<nums.length; j++){
sum=sum+nums[j];
if(sum>=target){
min = Math.min(min,j-i+1);
break;
}
}
}
return min==Integer.MAX_VALUE?0:min;
此方法在力扣上会超出时间限制
2.滑动窗口
int left=0;
int sum=0;
int result = Integer.MAX_VALUE;
for(int right=0; right<nums.length; right++){
sum+=nums[right];
while(sum>=target){
result = Math.min(result,right-left+1);
sum-=nums[left];
left++;
}
}
return result==Integer.MAX_VALUE?0:result;
int sum=0;
int result = Integer.MAX_VALUE;
for(int right=0; right<nums.length; right++){
sum+=nums[right];
while(sum>=target){
result = Math.min(result,right-left+1);
sum-=nums[left];
left++;
}
}
return result==Integer.MAX_VALUE?0:result;
1.滑动窗口的思想：就是两个指针，left表示窗口的左端开始，right表示窗口的右端结束，一开始是right一直往右移动，直到窗口之间的数之和大于等于target就会停止，记录窗口的长度，然后就是left往右移动判断和是否还是大于等于target，直到小于target就会停止，然后再移动right，由此反复，每次都会更新长度，最后result记录的就是最小长度
2.result的初始值记录为Integer.MAX_VALUE
Integer.MAX_VALUE表示int数据类型的最大取值数：2 147 483 647
Integer.MIN_VALUE表示int数据类型的最小取值数：-2 147 483 6483.最后的返回值也要判断，判断result是否赋值成功，不然的话就是整个数组之和都小于target，那么就会返回0
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK