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

简介: 剑指Offer面试题57 - II. 和为s的连续正数序列

aHR0cHM6Ly9jb2RpbmczbWluLm9zcy1hY2NlbGVyYXRlLmFsaXl1bmNzLmNvbS9jb2RpbmczbWluLzIwMjAvMDIvMjUvNUQ0RTJFMzY3RkRCNDIyRjkxQzNEMDc5N0QwNzdFQzcuanBn.png


前言

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

  1. 求和公式需要首项和末项,对应的就是a1和(a1+n-1)
  2. 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
}

aHR0cHM6Ly9jb2RpbmczbWluLm9zcy1hY2NlbGVyYXRlLmFsaXl1bmNzLmNvbS9jb2RpbmczbWluLzIwMjAtMDMtMDYtMDg1ODQxLnBuZw.png


方法二、暴力枚举


从1开始暴力枚举,初始子序列为[1,2],求和为3,对比和target的距离,如果小于就继续增加序列长度为[1,2,3]直到求和等于target则把序列加入最终结果集国;如果大于则改变序列起始数字为[2,3]继续寻找。


aHR0cHM6Ly9jb2RpbmczbWluLm9zcy1hY2NlbGVyYXRlLmFsaXl1bmNzLmNvbS9jb2RpbmczbWluLzIwMjAtMDMtMDYtMDkzMTUxLmpwZw.png

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


相关文章
|
10月前
【牛客面试必刷TOP101】有效括号序列、滑动窗口的最大值
【牛客面试必刷TOP101】有效括号序列、滑动窗口的最大值
|
11月前
|
机器学习/深度学习 人工智能 自动驾驶
强化学习从基础到进阶--案例与实践含面试必知必答[10]:模仿学习、行为克隆、逆强化学习、第三人称视角模仿学习、序列生成和聊天机器人
强化学习从基础到进阶--案例与实践含面试必知必答[10]:模仿学习、行为克隆、逆强化学习、第三人称视角模仿学习、序列生成和聊天机器人
强化学习从基础到进阶--案例与实践含面试必知必答[10]:模仿学习、行为克隆、逆强化学习、第三人称视角模仿学习、序列生成和聊天机器人
|
11月前
|
C++
剑指Offer - 面试题7:重构二叉树 (力扣 - 105、从前序与中序遍历序列构造二叉树)
剑指Offer - 面试题7:重构二叉树 (力扣 - 105、从前序与中序遍历序列构造二叉树)
42 0
|
11月前
|
机器学习/深度学习 人工智能 算法
强化学习从基础到进阶-常见问题和面试必知必答[1]:强化学习概述、序列决策、动作空间定义、策略价值函数、探索与利用、Gym强化学习实验
强化学习从基础到进阶-常见问题和面试必知必答[1]:强化学习概述、序列决策、动作空间定义、策略价值函数、探索与利用、Gym强化学习实验
|
11月前
Leecode 面试题57 - II. 和为s的连续正数序列
Leecode 面试题57 - II. 和为s的连续正数序列
38 0
LeetCode 面试题57 - II. 和为s的连续正数序列 LCOF
LeetCode 面试题57 - II. 和为s的连续正数序列 LCOF
|
存储
经典面试题:给两个序列如何构造一棵二叉树
在面试的过程中,我们经常会遇到一些数据结构相关的问题,很多经典问题百问不烂。而数据结构的问题中排序、链表、二叉树等问题又是经久不衰,这不,今天就分享一道关于经典的问题:给定两个序列如何构造一颗二叉树。
128 0
经典面试题:给两个序列如何构造一棵二叉树
|
SQL
SQL面试题:按照时间序列补全数据
HiveSQL面试题,根据时间以最新数据补全字段缺失值
572 0
|
Python
面试题57 - II. 和为s的连续正数序列
面试题57 - II. 和为s的连续正数序列
面试题57 - II. 和为s的连续正数序列
|
5天前
|
Java 程序员
Java this关键字详解(3种用法),Java程序员面试必备的知识点
Java this关键字详解(3种用法),Java程序员面试必备的知识点