前言
本系列文章为《剑指Offer》刷题笔记。
题目位置：力扣中国
题目
输入一个正整数 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
输入：target = 9 输出：[[2,3,4],[4,5]]
仔细观察输出不难看出 ：
- 输出一般是由两项，三项，四项构成的，都是越来越多的，所以循环从2开始查找数列，逐渐增加位数,所以每次循环数列长度就是n
- 题目要求每次输出的结果全部加起来等于target，用求和公式得到
等差数列求和公式(首项+末项) * n /2
转换为 ：(a1+(a1+n-1))*n/2
- 求和公式需要首项和末项，对应的就是a1和(a1+n-1)
- target/n 可以获得中位数，a1和中位数的距离为n/2
所以奇数的中位数-n/2，偶数的中位数是个小数，自动向下取整后剪去n/2后得到的值多减了1
例如：target为9，他长度n为3的子数列[2,3,4]，中位数是3,a1就是2，a1和中位数的距离就是n/2就是3-3/2=2 ； 他长度n为2的子数列[4,5]，中位数是4,a1就是4-2/2+1。
得到逻辑
if n%2 == 1{ a1 := target/n - n/2 }else{ a1 := target/n - n/2 + 1 }
简化为
a1 := target/n - n/2 - (n%2 - 1)
代码
go:
func findContinuousSequence(target int) [][]int { var res [][]int for n := 2; n < target; n++ { a1 := target/n - n/2 - (n%2 - 1) if a1 < 1 { break } if target == (a1+(a1+n-1))*n/2 { var res_col []int for i := a1; i < a1+n; i++ { res_col = append(res_col, i) } res = append(res, res_col) } } var revort_res [][]int for i:=len(res)-1;i>=0;i--{ revort_res = append(revort_res,res[i]) } return revort_res }
方法二、暴力枚举
从1开始暴力枚举，初始子序列为[1,2]，求和为3，对比和target的距离，如果小于就继续增加序列长度为[1,2,3]直到求和等于target则把序列加入最终结果集国；如果大于则改变序列起始数字为[2,3]继续寻找。
js:
var findContinuousSequence = function(target) { let arr = []; for (let i = 1; i < target - 1; i++) { let list = [i, i + 1]; while (add(list) <= target) { if (add(list) === target) { arr.push(list); } else { list.push(list[list.length - 1] + 1); } } } console.log(arr); return arr; }; function add(arr) { const reducer = (total, current) => total + current; return arr.reduce(reducer); }
