和为S的连续正数序列

1. 题目描述

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

2. 思路

• 暴力法
• 滑动窗口

3. 实现

3.1. 暴力法

//暴力法
//时间：O(N²)
//空间：O(N)
func FindContinuousSequence(sum int) [][]int {
	if sum <= 0 {
		return nil
	}

	res := make([][]int, 0)

	for i := 1; i < sum; i++ {
		current := make([]int, 0)
		current = append(current, i)
		currentSum := i
		for j := i + 1; j <= sum; j++ {
			if currentSum == sum {
				res = append(res, current)
				current = make([]int, 0)
				break
			} else if currentSum > sum {
				break
			} else {
				currentSum += j
				current = append(current, j)
			}
		}
	}

	return res
}

3.2. 滑动窗口

//时间复杂度：O(N)
//空间复杂度：O(1)
func FindContinuousSequence2(sum int) [][]int {
	if sum <= 0 {
		return nil
	}

	res := make([][]int, 0)
	currentSum := 0
	left := 1
	right := 1
	for left <= sum/2 {
		if currentSum < sum {
			currentSum += right
			right++
		} else if currentSum > sum {
			currentSum -= left
			left++
		} else {
			current := make([]int, 0)
			for i := left; i < right; i++ {
				current = append(current, i)
			}
			res = append(res, current)
			currentSum -= left
			left++
		}
	}
	return res
}

func findContinuousSequence(target int) [][]int {
    left := 1
    right := 1
    currentSum := 0
    var res [][]int
    for left <= target>>1 {
        if currentSum < target {
            currentSum += right
            right++
        } else if currentSum > target {
            currentSum -= left
            left++
        } else {
            current := make([]int, 0, right-left+1)
            for i := left; i < right; i++ {current = append(current, i)}
            res = append(res, current)
            currentSum -= left
            left++
        }
    }
    return res
}

4. 参考

• 和为S的连续正数序列_牛客题霸_牛客网
• 剑指 Offer 57 - II. 和为s的连续正数序列 - 力扣（LeetCode）