关于leetcode:Leetcode-题解系列-和为s的连续正数序列滑动窗口

48次阅读

共计 2719 个字符,预计需要花费 7 分钟才能阅读完成。

休了个不短不长的年假,题解系列持续动工~


本专题旨在分享刷 Leecode 过程发现的一些思路乏味或者有价值的题目。

题目相干

  • 原题地址: https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/]
  • 题目形容:

    输出一个正整数 target,输入所有和为 target 的间断正整数序列(至多含有两个数)。序列内的数字由小到大排列,不同序列依照首个数字从小到大排列。

    • 示例 1:
      输出 :target = 9
      输入:[[2,3,4],[4,5]]
    • 示例 2:
      输出 :target = 15
      输入 :[[1,2,3,4,5],[4,5,6],[7,8]]
      限度:1 <= target <= 10^5

    思路解析

暴力破解

题目的含意比拟清晰,需要求出和为特定值的 间断正整数序列。

首先,这道题的很间接的也会想到一个 — 暴力破解:

具体思路

  • 首先寻找是否存在满足要求的,以 1 为结尾的序列,所以初始化一个序列为 [1]
  • 顺次往序列里增加间断的正整数,让序列变成 [1, 2, 3..i. target],并且每次增加完一个整数时,比照以后序列所有整数之和 sum,与目标值 target 的关系

    • 如果sum < target,则持续往序列里增加下一个数;
    • 如果曾经满足 sum = target,那么 存储以后序列 ,并且阐明 以 1 开始的序列寻找能够进行了
    • 如果间接到 sum > target,那么阐明 以 1 开始的序列寻找能够进行了(不存在以 1 为结尾并且满足要求的序列);
  • 反复上述步骤,别离寻找以 2,3, … target 结尾且满足题意的序列;

下面这种思路的话 最坏的状况下,须要外层循环(外层循环也就是遍历以 1..n 结尾的序列)n次,内层循环 n 次(内层循环就是寻找以后结尾固定时,不同结尾的序列),那么总的复杂度就是 O(n^2),因为 1 <= target <= 10^5 , 所以O(n^2) 显著超时;

红色区域示意序列,它的左边界和右边界有个特点,都 只向右侧挪动,而整个遍历的过程,其实就像是一个推拉窗的挪动过程,这个算法也就由此得名。

滑动窗口

从上述过程能够看到,暴力破解的问题在于 工夫复杂度太高 ,而之所以高,是因为 在遍历过程存在一些能够跳过的过程 , 为了便于了解,咱们带入一个题设中的示例 1,target = 9 的状况来进行演示。依照暴力破解思路:

  • 首先序列为 [1] , 序列之和 sum = 1 , 1 < 9 持续循环;
  • 序列为 [1, 2] , 序列之和 sum = 3 , 3 < 9 持续循环;
  • 序列为 [1, 2,3] , 序列之和 sum = 6 , 6 < 9 持续循环;
  • 序列为 [1, 2, 3 ,4] , 序列之和 sum = 12 , 12 > 9 , 那 Stop!;
    到此阐明不存在 以 1 为结尾切满足要求的序列,那么依照后面的思路,接下来是要寻找以 2 结尾且满足题意的序列,那么当初问题来了:

咱们真的有必要从 [2] 开始吗?在找以 1 结尾的序列时,咱们曾经发现 [1,2,3] 之和都小于 target 了,那序列 [2,3] 之和必定也小于 9,那为什么还要循序渐进的,先走一次 [2] 再到 [2,3] 再到[2,3,4] 呢?

这,就是冲破的要害!

所以咱们发现,再找完以 i 结尾的序列之后,跳到寻找以 i + 1 结尾的序列时,是能够跳过一些两头遍历次数的,能够这么做:

  • 序列为 [1, 2, 3 ,4] , 序列之和 sum = 12,12 < 9,此时要进行寻找以 1 为结尾的序列 ,那么咱们间接去掉序列右边的值,从[2,3,4] 开始寻找以 2 结尾的序列;
  • 依照规定,[2, 3 ,4] 之和刚好为 9,此时保留以后序列后果,并且 进行寻找以 2 为结尾切满足要求的序列 ,接下来筹备寻找 3 结尾的序列,咱们 同样去掉此时序列的最右边值, 从 [3, 4] 开始运算;

反复上述过程,会发现,在遍历过程中,咱们的序列如下图所示(懒得做动图了,离开看更有利于了解):



红色区域示意序列,它的 左边界 右边界 有个特点,都 只向右侧挪动 ,而整个遍历的过程,其实就像是一个 推拉窗 的挪动过程,这个算法也就由此得名。

当然,要应用下面的算法,咱们要答复一个问题:相较于暴力破解,滑动窗口的确缩小了循环次数,然而滑动窗口是否找到所有的解呢?(也就是在上述的跳跃过程导致脱漏呢?)

这个是能够证实的,因为依照前文的遍历思路:

  • 寻找 1 结尾的序列时,只有序列之和小于 target,则 窗口右边界始终往右拓展 ,直到找到[1,2,3] 时,此时序列值之和还是小于 target; 而到[1,2,3,4] 时,此时序列之和第一次大于 target,阐明 以 1 结尾的序列寻找完结;
  • 那么此时以 2 结尾的序列 [2,3] < [1,2,3] < target,阐明 只须要从 [2,3,4] 开始寻找 就能够了,(读者敌人也能够拿示例 2 带入试试看,加深了解)以此类推,阐明滑动窗口的算法是不会有脱漏的。

残缺代码

到这里只须要整顿后面的思路,伪代码也就进去了:

  • 初始化,设定序列窗口的左右边界,别离为 1,2,而后开始循环;
  • 循环,当序列内之和小于 target 时,右边界右移;
  • 循环过程如果发现 序列值和等于 target,则存储以后序列,并且把左边界右移;
  • 循环过程如果发现 序列值和大于 target,则把左边界右移;
  • 当左边界追上右边界时,循环完结(能够思考下为什么?)

那么理论代码如下:

var findContinuousSequence = function(target) {const res = [];
  const sum = [0, 1];
  let l = 1; // 左边界
  let r = 2; // 右边界
  let s = 3; // 以后序列之和 sum
  while(l < r){if(s === target) {
          // 满足题意的序列增加到后果
          res.push(getList(l, r));
      }

      if(s > target) {
          s = s - l;
          l++;
      } else {
          r++;
          s += r; 
      }
  }
  return res;
};

function getList (l, r) {const res = [];
  for(let i = l; i<=r; i++) {res.push(i)
  }
  return res;
}

那么滑动窗口的内容就到此为止了~

此外 …


在文章开端顺便打个小广告,问下有没有想来外企 955 的小伙伴:

  • 面朝大海办公,不打卡 不考勤 到点就上班,工作生存两不误;
  • 假期超长(每年年假 + 带薪病假 + 企业年假 = 20 天起步!);
  • 而且很多岗位能够 长期近程办公!不再困扰与一线昂扬房价难落地的问题;
  • 可内推,base 杭州和厦门~

正文完
 0