给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。 进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
思路:
双指针法:
设定上下界,从0开始,右指针一直向右遍历,累加遍历过的值,当和大于等于s时,减去第一个值,如果还是大于等于s,减去第二个值,以此类推,一直遍历到最后。
提交的代码:
class Solution { public int minSubArrayLen(int s, int[] nums) { int i=0,j=0,sum=0,t=2147483647;//sum记录当前和,t记录当前和是几个值的相加 while(sum>=s||(i<nums.length&&j<nums.length)) //这里sum>=s比较重要,比如s=7,数组最后三项是2,4,3,如果不加,因为此时j已经达到退出循环的条件,会退出,然后sum=9,t=3;所以加这个条件使得继续执行else if中的操作 { if(sum<s) { sum+=nums[j]; j++; } else if(sum>=s) { if(j-i<t) { t = j-i; } sum-=nums[i]; i++; } } if(t==2147483647) { return 0; } return t; } }
完整的代码:
public class Solution209 { public static int minSubArrayLen(int s, int[] nums) { int i=0,j=0,sum=0,t=2147483647;//sum记录当前和,t记录当前和是几个值的相加 while(sum>=s||(i<nums.length&&j<nums.length)) { if(sum<s) { sum+=nums[j]; j++; } else if(sum>=s) { if(j-i<t) { t = j-i; } sum-=nums[i]; i++; } } if(t==2147483647) { return 0; } return t; } public static void main(String[] args) { int[] nums = {2,3,1,2,4,3}; int s = 7; System.out.println(minSubArrayLen(s,nums)); } }