42 和为S的连续正数序列

题目描述

输出所有和为S的连续正数序列。序列内按照从小到大的顺序，序列间按照开始数字从小到大的顺序。

示例：

输入: 9
输出: [[2,3,4], [4,5]]

解释: 2+3+4=9, 4+5=9

解题思路

核心思想：滑动窗口。维护一个窗口，窗口内的和为当前和。

关键步骤：

1. 初始窗口[1, 2]，和为3
2. 如果当前和 < target，窗口向右扩展
3. 如果当前和 > target，窗口左侧收缩
4. 如果当前和 == target，记录结果，窗口向右扩展

时间复杂度：O(target) 空间复杂度：O(1)

Python 实现

def find_continuous_sequence(target):
    """
    找出所有和为target的连续正数序列

    Args:
        target: 目标和

    Returns:
        list: 所有可能的序列
    """
    if target < 3:
        return []

    result = []
    left, right = 1, 2
    current_sum = 3

    while left < (target + 1) // 2:
        if current_sum == target:
            # 记录结果
            result.append(list(range(left, right + 1)))
            # 窗口向右扩展
            current_sum -= left
            left += 1
            right += 1
            current_sum += right
        elif current_sum < target:
            # 窗口向右扩展
            right += 1
            current_sum += right
        else:
            # 窗口左侧收缩
            current_sum -= left
            left += 1

    return result


# 测试代码
if __name__ == "__main__":
    test_cases = [9, 15, 3, 100]

    for target in test_cases:
        result = find_continuous_sequence(target)
        print(f"和为{target}的连续正数序列:")
        for seq in result:
            print(f"  {seq} (sum={sum(seq)})")
        print()

# 输出:
# 和为9的连续正数序列:
#   [2, 3, 4] (sum=9)
#   [4, 5] (sum=9)
#
# 和为15的连续正数序列:
#   [1, 2, 3, 4, 5] (sum=15)
#   [4, 5, 6] (sum=15)
#   [7, 8] (sum=15)
#
# 和为3的连续正数序列:
#   [1, 2] (sum=3)
#
# 和为100的连续正数序列:
#   [9, 10, 11, 12, 13, 14, 15, 16] (sum=100)
#   [18, 19, 20, 21, 22] (sum=100)

图解

滑动窗口示例: target=9

初始: left=1, right=2, sum=3

sum=3 < 9, 向右扩展
left=1, right=3, sum=6

sum=6 < 9, 向右扩展
left=1, right=4, sum=10

sum=10 > 9, 左侧收缩
left=2, right=4, sum=9

sum=9 = 9, 记录[2,3,4]
left=3, right=5, sum=12

sum=12 > 9, 左侧收缩
left=4, right=5, sum=9

sum=9 = 9, 记录[4,5]
left=5, right=6, sum=11

sum=11 > 9, 左侧收缩
left=6, right=6, left>=right, 结束

结果: [[2,3,4], [4,5]]