【面试题34】和为S的连续正数序列
2018-09-02 本文已影响0人
fighting_css
【题目】小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
【思路】
S除奇数时,如果余数为0时,存在这样的序列;
S除偶数时,如果余数为偶数的一半,则存在这样的序列;
需要确保序列的最左端(最小数)值大于0.
【代码】
res = []
for div in range(2,int(math.sqrt(tsum*2))+1):
if (div%2==0 and tsum%div == div/2) or (div%2==1 and tsum%div == 0):
start = tsum//div - div//2 + 1 if div%2==0 else tsum//div - div//2
res.append(list(range(start, tsum//div + div//2 + 1)))
return sorted(res)