「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

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

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

题目

思路

滑动窗口

方案代码

相关

相关推荐

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

`题目`

`思路`

`滑动窗口`