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 //返回位数
};
上一篇下一篇

猜你喜欢

热点阅读