【LeetCode】Python代码实现 之 面试题57 - II. 和为s的连续正数序列

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

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

示例 1：

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

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

解答：
滑动窗口法

def find_continuous_sequence(target):
    i, j, res = 1, 2, []
    # 滑动窗口的右边界不能超过target的中值
    while j <= target//2 + 1:
        cur_sum = sum(list(range(i, j+1)))
        # 若和小于目标，右指针向右移动，扩大窗口
        if cur_sum < target:
            j += 1
        # 若和大于目标，左指针向右移动，减小窗口
        elif cur_sum > target:
            i += 1
        else:
            res.append(list(range(i, j+1)))
            # 这里用j+=1，i+=1，i+=2都可以的
            j += 1

    return res


res = find_continuous_sequence(9)
print(res)

求根法：

def find_continuous_sequence(target):
    # 创建输出列表
    res = []

    # y不能超过target的中值,即y<=target//2 + 1,range函数左开右闭,所以这里是+2
    for y in range(1, target // 2 + 2):
        # 应用我们的求根公式
        x = (1 / 4 + y ** 2 + y - 2 * target) ** (1 / 2) + 0.5
        # 我们要确保x不能是复数，且x必须是整数
        if type(x) != complex and x - int(x) == 0:
            res.append(list(range(int(x), y + 1)))

    return res

最后

以上就是帅气月亮为你收集整理的【LeetCode】Python代码实现 之 面试题57 - II. 和为s的连续正数序列的全部内容，希望文章能够帮你解决【LeetCode】Python代码实现 之 面试题57 - II. 和为s的连续正数序列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。