©2020-2024 ioDraw All rights reserved,
Privacy Policy
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; } }