1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」——LCOF.57 – II. 和为s的连续正数序列

面试题57 - II. 和为s的连续正数序列

链接: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

思路

根据题意,我们开始想到的解法应该是双指针遍历。可以使用双指针范围内数组之和与target进行判断,符合条件的数组添加进入结果列表中,然后动态地维护两个指针缓缓前进,直到右边界到达target的中值即可。

现在我们先来了解一下什么叫滑动窗口

滑动窗口

可以先来先理解一下窗口的概念

假设target是9,我们的脑海中可以快速的浮现出一个从1到9的数组。这时候不妨再想象一下,数组下方有个两个指针,一个指向1,一个指向5,两个指针形成的这个数组范围,就是所谓的窗口。如下图所示:

请问滑动作何解释?
左右指针通过平移,会改变了窗口的范围,从而引起窗口的滑动,这就是所谓的滑动窗口

针对目前这个题,我们可以把左指针i指向1,右指针j指向2,然后就能计算出当前窗口范围各数字的和,cur_sum = sum(list(range(i,j+1))),如果cur_sum小于target,说明当前窗口数字之和过小,这时候咱们可以令j += 1,这样我们的新窗口就向右边扩大了。同样的道理,如果cur_sum大于target,这说明我们当前窗口数字之和过大,这时候就令i += 1,这样窗口的左边界就向右边移动了一个单位,就使得窗口变小了。

观察上图,前面窗口的指针是i=1,j=5,形成的窗口就是[1,2,3,4,5],那么cur_sum就是1+2+3+4+5=15

由于左指针i向右平移,后面窗口的指针是i=4,j=5,形成的窗口就是[4,5],那么cur_sum就是4+5=9

代码如下:

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        # 初始化窗口指针和输出列表
        i, j, res = 1,2, []

        # 滑动窗口的右边界不能超过target的中值
        while j <= target//2 + 1:
            # 计算当前窗口内数字之和
            cur_sum = sum(list(range(i,j+1)))
            # 若和小于目标,右指针向右移动,扩大窗口
            if cur_sum < target:
                j += 1
            # 若和大于目标,左指针向右移动,减小窗口
            elif cur_sum > target:
                i += 1
            # 相等就把指针形成的窗口添加进输出列表中
            # 别忘了,这里还要继续扩大寻找下一个可能的窗口哦
            else:
                res.append(list(range(i,j+1)))
                # 这里用j+=1,i+=1,i+=2都可以的
                j += 1
        
        return res

这题其实还能把公式写出来,留给大家探索吧。

方案代码

双指针解法:

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        i, j, res = 1,2, []
        while j <= target//2 + 1:
            cur_sum = sum(list(range(i,j+1)))
            if cur_sum < target:
                j += 1
            elif cur_sum > target:
                i += 1
            else:
                res.append(list(range(i,j+1)))
                j += 1
        return res

原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/206.html