美文网首页
(面试题57 - II)和为s的连续正数序列

(面试题57 - II)和为s的连续正数序列

作者: 等不了天明等时光 | 来源:发表于2020-03-17 12:50 被阅读0次

解题思路

设数列第一项为t,项数为n,则由等差数列求和公式 [t+(t+n-1)]*n/2 = s,
化简得 t = [s-n(n-1)/2]/n,因为t为正整数,所以 s>n(n-1)/2,[s-n(n-1)/2] % n = 0。又项数至少为2,所以n>=2。
步骤:
1)初始化项数 n=2,结果数列res = [];
2)进行循环,当 n(n-1)/2 < s时,即 while(n(n-1)/2 < s):
2.1)判断[s-n(n-1)/2]能否整除n,即[s-n(n-1)/2] % n = 0,是则进行如下操作:求出 t,并根据当前项数n求出整个数列,加入结果数列中。
2.2)否则项数加1,继续循环;
3)由于项数是从小到大,所以数列是以从大到小的顺序存入结果数列的,最后需要进行反转操作。

代码

class Solution:
    def findContinuousSequence(self, target: int) -> List[List[int]]:
        #初始化项数为2
        n = 2
        res = []
        while n*(n-1)/2 < target: # 必须为正数
            if (target - n*(n-1)/2) % n == 0: #判断是否能够整除
                t = int((target - n*(n-1)/2) / n) # float转int
                res.append(list(range(t, t+n)))
            n += 1
        # 数列反转
        return res[::-1]

相关文章

网友评论

      本文标题:(面试题57 - II)和为s的连续正数序列

      本文链接:https://www.haomeiwen.com/subject/yiftyhtx.html