面试题57 - II. 和为s的连续正数序列

[yankewei]

输入一个正整数 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

解法

感觉这种连续的序列什么的，可以使用滑动窗口解决，因为窗口中的数字都是有规律的

func findContinuousSequence(target int) [][]int {
    var ret [][]int
    s := make([]int, target)
    for i := 0; i < target; i++ {
        s[i] = i + 1
    }
    var l, r int
    for l < target-1 && r < target-1 {
        add := (s[l] + s[r]) * (r - l + 1) / 2
        if add == target {
            r++
            ret = append(ret, s[l:r])
        } else if add > target {
            l++
        } else {
            r++
        }
    }
    return ret
}