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

109 阅读 0 评论 72 点赞

我是靠谱客的博主踏实微笑，这篇文章主要介绍Leetcode 面试题57 - II.和为s的连续正数序列Leetcode 面试题57 - II.和为s的连续正数序列，现在分享给大家，希望可以做个参考。

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

1 题目描述（Leetcode题目链接）

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

复制代码

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

复制代码

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

2 题解

滑动窗口，窗口之和小于target就继续网上加，大于target就一直减去前面的数知道小于等于target，如果等于target窗口就是一个解。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        retv = []
        length = target//2 + 1
        curr = [1]
        for j in range(2, length + 1):
            curr.append(j)
            while sum(curr) > target:
                curr.pop(0)
            if sum(curr) == target:
                retv.append(copy.deepcopy(curr))
                curr.pop(0)
        return retv