题目描述

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例

示例 1：

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

示例 2：

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

解答方法

方法一：滑动窗口法(双指针法）

思路

https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/shi-yao-shi-hua-dong-chuang-kou-yi-ji-ru-he-yong-h/

代码

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

时间复杂度

O(target)

空间复杂度

O(1)