题解 | #和为S的连续正数序列#
和为S的连续正数序列
https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param sum int整型 # @return int整型二维数组 # class Solution: def FindContinuousSequence(self , sum: int) -> List[List[int]]: # write code here rst=[] if sum < 3: return rst end = max(3,sum // 2) for i in range(2,end): # i代表l的长度 if i % 2 == 0: if sum % i != 0: m = sum % i if m == i // 2: base = sum // i - m + 1 if base > 0 : # 因为序列中的数必须为正数 l = [base+j for j in range(0,i)] rst.append(l) else: if sum % i == 0: base = sum // i - i // 2 if base > 0: l = [base+j for j in range(0,i)] rst.append(l) return rst[::-1]
事先找规律:
我们循环遍历序列长度为2到S/2的可能性。
当序列长度i为奇数,则当S能被i整除时,可以获得一个序列:[S/i-i//2...,S/i,...S/i+i//2]。
当序列长度i为偶数,则当S不能被i整除时,可以获得一个序列:[S/i-i//2+1,S//i,S//i+i//2]。