美文网首页
leecode算法题209:双索引,滑动

leecode算法题209:双索引,滑动

作者: 小强不是蟑螂啊 | 来源:发表于2019-06-12 19:51 被阅读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 //返回位数
    };

    相关文章

      网友评论

          本文标题:leecode算法题209:双索引,滑动

          本文链接:https://www.haomeiwen.com/subject/byjrfctx.html