leecode算法题209:双索引,滑动
2019-06-12 本文已影响0人
小强不是蟑螂啊
题目:给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。
例子:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
解题思路:用左右边界组成一个子数组,实现累加,当和大于s时,子数组左边向右移动以为,子数组右边向右移动一位,当判断的值不小于s时,判断位数和之前位数的大小,保存最小位数,最后返回。
函数:
var minSubArrayLen = function(s,arr) {
var l = 0,r = -1; //定义左右边界
var sum = 0,n=arr.length;
var len = n+1;
while(l<n){
if(sum <s){ //小于是子数组右边边界右移一位
sum += arr[++r]
} else { //不小于子数组边界左移一位
sum -= arr[l++];
}
if(sum>=s){ //当符合条件是比较最小位数保存
len = Math.min(len,r-l+1)
}
}
if(len == n+1) {
return 0;
}
return len //返回位数
};