美文网首页
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:双索引,滑动

    题目:给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如...

  • Leetcode 长度最小的子数组

    题目描述 leecode第209题:长度最小的子数组[https://leetcode-cn.com/proble...

  • LeeCode算法题

    此篇文章将记录我在LeeCode上刷过的题目与解答。 难度由简单开始。 两数之和 给定一个整数数组 nums和一个...

  • 滑动窗口算法

    一、滑动窗口算法 也会使用两个指针,但和双指针算法不同的是双指针算法关注的往往是两个指针正在指向的两个元素,而滑动...

  • 记一次面试中的算法题(两数之和)

    前段时间,有次面试中遇到一道算法题,感觉答的不是很好,后面查相关资料发现竟然就是LeeCode上的原题。。。 题目...

  • 无重复最长子串

    算法:滑动窗口关键变量: 窗口左边沿索引 lk, 窗口右边沿索引 rk, 目前最长子串长度 ans,记录窗口内字...

  • 『算法』『数据结构』 浅谈滑动窗口算法(思想)[双指针法中的左右

    基本认识 滑动窗口算法的本质是双指针法中的左右指针法,滑动窗口算法是双指针法中的左右指针法更为形象的一种表达方式。...

  • 递归玩转动态规划

    汇总LeeCode前200题中所有涉及动态规划的算法题,用自己的逻辑整理此类问题的优化思路。 概述 最长回文子串 ...

  • leecode中字符串报数的js算法实现

    作为一个前端,对于算法还是挺感兴趣的,也是为了实力,最近在看leecode看一些算法,今天碰到一道题,开始的时候感...

  • 数组

    二分法,快排序,归并28327268088215对撞指针12534434511双索引技术,滑动窗口209343876

网友评论

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

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