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

2020年3月6日 评论 273 views 1510字阅读5分2秒

前言

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

例如:target9,他长度n为3的子数列[2,3,4],中位数是3,a1就是2a1和中位数的距离就是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);
        }
weinxin
公众号
在号内与我交流,回复【资源】获取技术大礼包
小熊