和为S的连续正数序列

方法1:暴力求解

用两个数字begin和end分别表示序列的最大值和最小值,

首先将begin初始化为1,end初始化为2.

如果从begin到end的和大于s,我们就从序列中去掉较小的值(即增大begin),

相反,只需要增大end。

终止条件为:一直增加begin到(1+sum)/2并且end小于sum为止

思路2:

1)由于我们要找的是和为S的连续正数序列,因此这个序列是个公差为1的等差数列,而这个序列的中间值代表了平均值的大小。假设序列长度为n,那么这个序列的中间值可以通过(S / n)得到,知道序列的中间值和长度,也就不难求出这段序列了。

  2)满足条件的n分两种情况:

n为奇数时,序列中间的数正好是序列的平均值,所以条件为:(n & 1) == 1 && sum % n == 0;(n为奇数且n 能被sum整除)

n为偶数时,序列中间两个数的平均值是序列的平均值,而这个平均值的小数部分为0.5,所以条件为:(sum % n) * 2 == n.(小数部分为0.5,说明余数是除数的一半)

  3)由题可知n >= 2,那么n的最大值是多少呢?我们完全可以将n从2到S全部遍历一次,但是大部分遍历是不必要的。为了让n尽可能大,我们让序列从1开始,

根据等差数列的求和公式:S = (1 + n) * n / 2,{ 备注:  Sn=n*(a1+an)/2  }得到

.

  最后举一个例子,假设输入sum = 100,我们只需遍历n = 13~2的情况(按题意应从大到小遍历),n = 8时,得到序列[9, 10, 11, 12, 13, 14, 15, 16];n  = 5时,得到序列[18, 19, 20, 21, 22]。

完整代码:时间复杂度为

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 题目描述 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并...
    Gxxx_xx阅读 1,278评论 1 0
  • 在C语言中,五种基本数据类型存储空间长度的排列顺序是: A)char B)char=int<=float C)ch...
    夏天再来阅读 4,109评论 0 2
  • 本系列导航:剑指offer(第二版)java实现导航帖 面试题57.2:和为s的连续正数序列 题目要求:输入一个整...
    ryderchan阅读 629评论 0 2
  • 这本书的作者是古典,非常有意思的名字,恰如这本书一样有意思。这位作者是知乎上的一位大咖极的人物,对人生规划有独道的...
    伪悔到来阅读 295评论 0 0
  • 当初的离别闹得很不愉快,或许都谈不上离别,因为离别往往是两个人的纠缠与不舍,带着让人心碎的美感,而当初她的离开很荒...
    冰柳阅读 395评论 0 0

友情链接更多精彩内容