题解 | #和为S的连续正数序列#

class Solution:
    def FindContinuousSequence(self , sum: int) -> List[List[int]]:
        # write code here
        res = []
        if sum in [0, 1, 2]:
            return None

        max_len, len = 2, 2

        while sum >= len * (len + 1) / 2:  # 最大长度len, (1,2,...,len)应小于sum
            max_len = len
            len += 1
        len = max_len

        while len > 1:
            ave = sum // len
            if sum % len == 0:  # 长度奇数sum必须除尽
                if len % 2 == 1:  
                    nums = []
                    for i in range(ave-len//2, ave+len//2+1, 1):
                        nums.append(i)
                    res.append(nums)
            else:  # 长度为>2的偶数,  连续数均值小数位必为0.5（2,3,4,5）-> 3.5
                if len % 2 == 0:
                    if sum % len / len == 0.5:
                        nums = []
                        for i in range(ave-len//2+1, ave+len//2+1, 1):
                            nums.append(i)
                        res.append(nums)

            len -= 1

        return res

时间复杂度O(√n*√n）

空间复杂度O(√n）