牛客网 和为S的连续正数序列
题目：
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
解法：
自己的想法是利用(a1+an)*n/2=Sum，以及an-a1=n-1的关系求出结果。解法如下，
# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
# n 为序列的最大长度
n=tsum//2+1
tmp_n=n
# 根据公式（a1+an）*n/2=tsum
res=[]
while tmp_n>1 :
if (2*tsum/tmp_n+1-tmp_n)>0 and (2*tsum/tmp_n+1-tmp_n)%2==0:
a1 = (2 * tsum / tmp_n + 1 - tmp_n) / 2
cur_ans=[(a1+i) for i in range(tmp_n)]
res.append(cur_ans)
tmp_n=tmp_n-1
return res但是没有通过测试用例15，在本机上运行通过[[1.0, 2.0, 3.0, 4.0, 5.0], [4.0, 5.0, 6.0], [7.0, 8.0]]，但是在牛客网上提交时显示输出为[[1,2,3,4,5],[2,3,4,5],[4,5,6],[7,8]]，多出来一个[2,3,4,5]，不知道是怎么出来的，为了筛去这些不正确的结果，增加了一个判断，最终解法如下：
# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
# n 为序列的最大长度
n=tsum//2+1
tmp_n=n
# 根据公式（a1+an）*n/2=tsum
res=[]
while tmp_n>1 :
if (2*tsum/tmp_n+1-tmp_n)>0 and (2*tsum/tmp_n+1-tmp_n)%2==0:
a1 = (2 * tsum / tmp_n + 1 - tmp_n) / 2
cur_ans=[(a1+i) for i in range(tmp_n)]
if sum(cur_ans)==tsum:
res.append(cur_ans)
tmp_n=tmp_n-1
return res另一解法：参考和为S的连续正数序列
# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
if tsum < 3:
return []
small = 1
big = 2
middle = (tsum + 1)>>1
curSum = small + big
output = []
while small < middle:
if curSum == tsum:
output.append(range(small, big+1))
big += 1
curSum += big
elif curSum > tsum:
curSum -= small
small += 1
else:
big += 1
curSum += big
return output本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年08月08日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录