jz057II.和为s的正数序列

题目链接

有了解决jz057I的经验，我们也考虑用两个数small和big分别表示序列的最小值和最大值。首先把small初始化为1，big初始化为2。如果从small到big的序列的和大于s，则可以增大big，让这个序列包含更多的数字。因为这个序列至少要有两个数字，我们一直增加small直到$\frac{1 + s}{2}$为止。这个算法的时间复杂度是O（N），空间复杂度是O（1）。当然，这题还有其他更快的用方程求解的方法，鉴于不是很通用我就不在这里写了。

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        res = []
        if target < 4:
            return res
        left, right, s = 1, 2, 1
        while left < (target + 1)/2 and left < right:
            if s < target:
                s += right
                right += 1
            elif s > target:
                s -= left
                left += 1
            else:
                res.append(list(range(left, right)))
                s -= left
                left += 1
        return res

PREVIOUSjz057I.和为s的数字

NEXTjz058I.翻转单词顺序