题解 | #和为S的连续正数序列#
和为S的连续正数序列
https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe
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)