剑指 Offer 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

解法一：哈希表 + 前缀和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func findContinuousSequence(target int) [][]int {
    arr := make([]int, target)
    for i := 1; i <= target; i++ {
        arr[i-1] = i
    }
    record := make(map[int]int)
    sum := 0
    var ans [][]int
    record[0] = 0
    for i := 1; i <= target-1; i++ {
        sum += i
        if idx, has := record[sum-target]; has {
            ans = append(ans, arr[idx:i])
        }
        record[sum] = i
    }
    return ans
}