美文网首页
(面试题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