力扣LeetCode【每日一题】—— 面试题解答57 - II. 和为s的连续正数序列（Python3）滑动窗口

最新推荐文章于 2025-02-21 16:40:04 发布

在家慢慢长胖

最新推荐文章于 2025-02-21 16:40:04 发布

阅读量160

点赞数

文章标签： python

本文链接：https://blog.csdn.net/csdn_yanice/article/details/104705917

版权

难度：简单（LZ最近发现越是简单的题，解答方式越多）

类型：双指针、滑动窗口

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

示例 1：

input：target = 9
output：[[2,3,4],[4,5]]

示例 2：

input：target = 15
output：[[1,2,3,4,5],[4,5,6],[7,8]]

解法1：暴力法哈哈哈！第一反应还是暴力，是我太菜了

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        raw = list(range(1, ((target+1)//2 + 1))) # 建议转list，方便后续切片和append
        output = []
        for i in range(len(raw)):
            for j in range(i + 1, len(raw)):
                if sum(raw[i: j+1]) == target:
                    output.append(raw[i: j+1]) 
                elif sum(raw[i: j+1]) < target:
                    j += 1
                else: break
        return output

解法2：滑动窗口（模拟双指针）

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        i, j, s = 1, 1, 0 # 滑动窗口的左、右边界及总和
        output = []
        while i <= target // 2:
            if s < target:
                s += j
                j += 1 # 右边界右移1
            elif s > target:
                s -= i
                i += 1 # 左边界右移1
            else:
                output.append(list(range(i, j)))
                s -= (2*i + 1)
                i += 2 # 左边界右移2格，移1格无解
        return output