题目链接: 剑指 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
}