剑指Offer面试题57 – II. 和为s的连续正数序列

前言

本系列文章为《剑指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]]

仔细观察输出不难看出 ：
1. 输出一般是由两项，三项，四项构成的，都是越来越多的，所以循环从2开始查找数列，逐渐增加位数,所以每次循环数列长度就是n
2. 题目要求每次输出的结果全部加起来等于target，用求和公式得到
等差数列求和公式(首项+末项) * n /2
转换为 ：(a1+(a1+n-1))*n/2
3. 求和公式需要首项和末项，对应的就是a1和(a1+n-1)
4. 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
}

时间复杂度 O(logn)：执行次数是对数的；
空间复杂度 O(N*N)：申请了很多二维数组空间。

方法二、暴力枚举

从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);
        }