剑指Offer[57-2]-和为s的连续正数序列

题目

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

示例:

输入:target = 9
输出:[[2,3,4],[4,5]]

输入:target = 15
输出:[[1,2,3,4,5],[4,5,6],[7,8]]

python代码

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        left,right = 1,1
        outlist = []
        _sum = 0
        while left <= target // 2:
            if _sum < target:
                _sum+=right
                right+=1
            elif _sum > target:
                _sum-=left
                left+=1
            else:
                outlist.append([_ for _ in range(left,right)])
                _sum-=left
                left+=1
        return outlist

这道题考察的是逻辑,使用滑动窗口法可以很直观地解决,整体思路就是:

  • 我们初始化一个窗口, left,right = 1,1;
  • 然后判断窗口内的和是否等于target,若小于target,则将右指针向右移动,此时窗口进入了一个新值,和就变大了;若大于target,则将左指针向右移动,此时窗口删除了一个值,和就变小了。就这样每次根据当前窗口内的值的和来调整窗口,直到和等于target;
  • 若找到一组序列,就记录一组,然后将左指针向右移动,开始寻找下一组

注意:每次调整窗口前,都要先从_sum中减去或加上相应的值

为什么while left <= target // 2?

其实很好理解,若一个值A写成两个数相加的形式,则这两个数不可能同时大与A的中值。
A = x+y,若x > A/2 and y > A/2,则x + y > A,推广到序列,当窗口的左边界值>target//2时,序列的和一定大于target。

发表评论

电子邮件地址不会被公开。