每日一题-6

题目描述

输入一个正整数 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

解题思路

1.暴力枚举，没啥说的，一直循环求和，等于target的加到数组里面
2.滑动数组
首先start指向1，end指向2。这是初始状态
判断start到end的总和sum与target的大小
如果sum<target:
end+=1#右边界往后滑动
如果sum==target:
[start...end]就是一个结果
如果sum>target:
start+=1#左边界往后移动，在start到end的区间里，寻找符合条件的结果
这个有一点影响时间的就是我使用的乘法计算sum，用加法时间会更短。有兴趣的可以看下面这个题解，原链接讲的更加仔细。

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

作者：nettee
链接：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/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

代码

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        #暴力枚举
        # start = 1
        # end = 1
        # L1 = []
        # flag = True
        # while(flag):
        #     sum = 0
        #     for i in range(start, target):
        #         sum+=i
        #         end = i
        #         if(sum==target):
        #             start+=1
        #             break
        #         if(sum>target):
        #             if (end-start)==1:
        #                 flag = False
        #             start+=1
        #             break
        #     if(sum==target):
        #         L1.append(list(range(start-1, end+1)))    
        #         if (end-start+1)==1:    
        #             flag = False
        # return L1

        #滑动数组
        start = 1
        end = 2
        L = []
        while start<end:
            sum = (start+end)*(end-start+1)//2
            if(sum>target):
                start+=1
            elif(sum==target):
                L.append(list(range(start, end+1)))
                start+=1
            else:
                end+=1
        return L