力扣面试题57 - II. 和为s的连续正数序列详解滑动窗口法 python3实现

68 阅读 0 评论 45 点赞

我是靠谱客的博主老迟到小猫咪，最近开发中收集的这篇文章主要介绍力扣面试题57 - II. 和为s的连续正数序列详解滑动窗口法 python3实现，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

和为s的连续正数序列

题目：

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

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

来源：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof

示例:

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

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

解析如下：

滑动窗口是什么？：

滑动窗口可以看作是数组框起来的一部分。在一些数组类题目中，可以用滑动窗口来观察可能的候选结果。当滑动窗口从数组的左边滑到右边，则可以从所有可能的候选结果中找到最优解。

以本题为例，正整数序列1，2，3，…,n，可以视为数组，滑动窗口左边界为left，右边界为right，则为滑动窗口框起来的一个区间。
在这里插入图片描述
滑动窗口最重要的性质是：窗口的左边界和右边界永远只能向右移动，而不能向左移动。
滑动窗口只有**右边界向右移动（扩大窗口）和左边界向右移动（缩小窗口）**两个操作。

通过本题来理解滑动窗口：

这道题中，我们关注的是滑动窗口中所有数的和。当滑动窗口的右边界向右移动时（扩大窗口），right+=1,窗口中就多了一个数字，窗口中数字的和也就要加上right。与之同理，当滑动窗口的左边界向左移动时（减小窗口），left+=1,窗口中就少了一个数字，窗口中数字的和也就要加上left。

当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动
当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动
当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [left,right]，那么我们已经找到了一个 left 开头的序列，也是唯一一个 left开头的序列，接下来需要找 left+1开头的序列，所以窗口的左边界要向右移动，继续寻找。

那么，这个不停寻找的停止条件是什么？
当left等于target的一半时，循环停止，因为当left大于一半时，一不存在连续的整数相加可以等于target了。
如： target = 9 5 + 6 就一定大于9了
target = 4 2 + 3 也大于4.

下面以target=5来演示滑动窗口的过程：

初始的left = 1,right = 2，（因为必须有两个数相加），则sum = 3.
在这里插入图片描述
如图，[[2,3]]为所求结果。

代码如下

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        left = 1
        right = 2
        num_sum = 3
        res = []

        while right <= target / 2 + 1:
            if num_sum < target:
                right +=1
                num_sum += right
                
            elif num_sum > target:
                num_sum -= left
                left +=1
                
            else:
                arr = list(range(left,right+1))
                res.append(arr)
                num_sum -=left
                left +=1

        return res