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]]

限制：
1 <= target <= 10^5

数学

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        res = []
        for i in range(1, target // 2 + 1):
            for j in range(i + 1, target // 2 + 2):
                if (i + j) * (j - i + 1) // 2 == target:
                    res.append(list(range(i, j + 1)))
                    break
                if (i + j) * (j - i + 1) // 2 > target:
                    break
        return res

滑动窗口
滑动窗口的重要性质是：窗口的左边界和右边界永远只能向右移动，而不能向左移动。这是为了保证滑动窗口的时间复杂度是 O(n)。如果左右边界向左移动的话，这叫做“回溯”，算法的时间复杂度就可能不止 O(n)。在这道题中，我们关注的是滑动窗口中所有数的和。当滑动窗口的右边界向右移动时，也就是 j = j + 1，窗口中多了一个数字 j，窗口的和也就要加上 j。当滑动窗口的左边界向右移动时，也就是 i = i + 1，窗口中少了一个数字 i，窗口的和也就要减去 i。滑动窗口只有右边界向右移动（扩大窗口）和左边界向右移动（缩小窗口）两个操作，所以实际上非常简单。

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

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        i = j = 1
        res = []
        cur_sum = 0
        while j <= target // 2 + 1: # 右边界不超过中值
            cur_sum += j
            j += 1
            while cur_sum > target:
                cur_sum -= i
                i += 1
            if cur_sum == target:
                res.append(list(range(i, j)))
        return res

因为是连续的正数序列，i+1 开头的序列一定无解，所以当sum==target时，左边界可以直接向右移动两位，即i += 2，这样子时间复杂度会稍微小一点点。

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        l = 1
        r = 2
        res = []
        
        while l <= target//2:
            sum = (l+r)*(r-l+1)//2  # 等差数列求和公式求sum
            if sum < target:
                r += 1
            elif sum == target:
                add = list(range(l,1+r))
                res.append(add)
                l += 2
            elif sum > target:
                l += 1
        return res