Continuous Positive Sequences with Sum S

This is a historical learning note and may contain outdated or incomplete understanding.

1. Problem Description

Xiaoming likes mathematics very much. One day, while doing his math homework, he was asked to calculate the sum from 9 to 16 and immediately wrote the correct answer, 100. But he was not satisfied with that and wondered how many sequences of consecutive positive integers sum to 100 (with at least two numbers). Soon he found another consecutive positive sequence summing to 100: 18,19,20,21,22. Now the problem is yours: can you quickly find all consecutive positive-integer sequences whose sum is S? Good Luck!

2. Approach

Brute force
Sliding window

3. Implementation

3.1. Brute Force

// Brute force
// Time: O(N²)
// Space: 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. Sliding Window

// Time complexity: O(N)
// Space complexity: 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
}