1.题目

给定一个含有 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

2.三种解法

(1)暴力解法

       
这道题可以从第一位(小于目标值)开始一直依次向后加,直到加到大于目标值,开始计算开始到结束的距离,然后进行第二个数依次向后加的行为,比较最小距离,因此使用双重循环,实现查找最小距离的方式,当查找到第一次出现大于目标值的距离时,后续可以不用在查找,进入下一次的循环查找,可以加快运行速度。代码展示:
class Solution { public int minSubArrayLen(int target, int[] nums) { int
min=Integer.MAX_VALUE; for(int i=0;i<=nums.length-1;i++){ int sum=0; for(int
j=i;j<=nums.length-1;j++){ sum+=nums[j]; if(sum>=target){
min=Math.min(min,j-i+1); break; } } } return min==Integer.MAX_VALUE?0:min; } }
(2) 双指针解法

       
即使使用暴力可以运行出结果,但运行速度还是有点慢,使用双指针可以加快运行速度,双指针的解题思路是:首先定义两个指针,将j作为首指针看待,如例1数组为[2,3,1,2,4,3]所看,先将2放入,对比是否大于目标值,不大于就继续向后进行累加,当累加大于目标值时,进行最小距离的赋值,这时总和减去i代表的尾指针,再进行判断,若小于目标值进行累加,若加上后一位和大于目标值,再进行减去尾指针的操作,当出现距离小于之前判断的值进行重新最小值赋值。代码展示:
class Solution { public int minSubArrayLen(int target, int[] nums) { int
i=0,j=0,sum=0; int min=Integer.MAX_VALUE; while(j<nums.length){ sum+=nums[j++];
while(sum>=target){ min=Math.min(min,j-i); sum-=nums[i++]; } } return
min==Integer.MAX_VALUE?0:min; } }
(3) 二分查找

       
此题还可以使用二分查找方法,给一个全新的数组进行存储sum值,要考虑长度匹配问题,例如sum[1]=nums[0]、sum[2]=nums[0]+nums[1],为了节省时间直接在程序中调用二分查找语句,但因为底层代码问题,需要判断k是否小于0,若小于0进行按位取反,是为了保证左边界和右边界在数组内,然后进行最小值比较赋值,代码展示:
class Solution { public int minSubArrayLen(int target, int[] nums) { int[]
sum=new int[nums.length+1]; int min=Integer.MAX_VALUE; for(int
i=1;i<=nums.length;i++){ sum[i]=sum[i-1]+nums[i-1]; } for(int
j=0;j<sum.length;j++){ int index=target+sum[j]; int
k=Arrays.binarySearch(sum,index); if(k<0){ k = ~k; } if(k<=nums.length){
min=Math.min(k-j,min); } } return min==Integer.MAX_VALUE?0:min; } }

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信