剑指 Offer 57 - II. 和为s的连续正数序列

题目链接： 剑指 Offer 57 - II. 和为s的连续正数序列

题目描述：

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

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

解法思路：

双指针：
当总和小于 target 时，j 指针向后移动，直到 大于或等于停止
判断此时sum :

• 若 等于 target ，则 放入答案，
• 然后 i 指针向后移动，并从 sum 中减去

代码：

func findContinuousSequence(target int) [][]int {
    res := [][]int{}
    sum := 1
    for i,j := 1,1;i < target;i++{
        for sum < target{
            j++
            sum += j 
        }
        if sum == target {
            var path  []int
            for k :=i ; k <= j; k++{
                path = append(path,k)
            } 
            res = append(res,path)
        }
        sum -= i
    }
    return res
}

滑动窗口：

• 利用 l,r 作为边界维护滑动窗口和总值
• 当和总值小于 target，r++ 向右扩大滑动窗口
• 当和总值大于 target，l++ 向右缩小滑动窗口
• 当和总值等于 target，存储当前 [l,r] 的排序，并继续 l++ 向右缩小滑动窗口

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