题解 | #和为S的连续正数序列#
和为S的连续正数序列
https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe
思路：反向看：如果存在这样的连续序列，必有公式：S=n*(n+1)/2。
解读公式：
n是偶数，n+1必是奇数，sum/n = (n+1)/2必是x.5类型。
n是奇数，n+1必是偶数，sum/n = (n+1)/2必是整数类型。
步骤：
从i=2开始作为因子。i=i+1循环。（从2作因子递增循环，结果要倒序。否则就从边界递减循环，不需要倒序，见下。）
如果因子是偶数，看除法结果是否是x.5类型。如果是，就添加序列。(例如9/2=4.5，则可以添加[4,5])
如果因子是奇数，看除法结果是否是整数类型。如果是，就添加序列。(例如9/3=3，则可以添加[2,3,4])
注意：
要提防序列左边突破到0的情况（例如21/7=3, 而[0,1,2,3,4,5,6]是非法的，因为只能是正整数）
两种解决思路：
1.循环内部多进行一个判断，以防突破到0。时间复杂度其实也是 ~O(sqrt(n)*sqrt(n))，但比下个方法多一些时间
2.本题解决思路：
边界的情况，就是“ sum = 2x * x ”中的2x，只需循环到2x即可。
边界条件: b = 2 * int(math.sqrt(target // 2)) + 1 # 一般边界
# 考虑45=9*5(合法), 10=5*2非法。
# 总结就是 2*右因子>左因子
boundary = b if 2 * target / b > b else b - 1
# 考虑45=9*5(合法), 10=5*2非法。
# 总结就是 2*右因子>左因子
boundary = b if 2 * target / b > b else b - 1
思路2的好处，可以避免循环内部多余的判断。时间复杂度为 ~ O(sqrt(n)*sqrt(n)) ~ O(n)
import math class Solution: def FindContinuousSequence(self, sum): if sum == 1: return [] res = [] # 这里按照 2*n*n ≈ sum，来确定循环的边界到 2*n 即可。 # 时间复杂度更低: ~O(sqrt(n)*sqrt(n)) ~ O(n)。 # 全循环时间更多(虽然复杂度一样)，内部要判断：序列左边是否会突破到0 b = 2 * int(math.sqrt(sum // 2)) + 1 # 一般边界 # 考虑45=9*5(合法),10=5*2非法。 # 总结就是 2*右因子>左因子 boundary = b if 2 * sum / b > b else b - 1 i = 2 while i <= boundary: # 奇数 if i % 2: # 能整除就行 if not sum % i: res.append( [x for x in range(sum // i - i // 2, sum // i + i // 2 + 1)] ) # 偶数 else: # 结果必须是x.5的形式 if not (2 * sum) % i and sum % i: res.append( [x for x in range(sum // i - i // 2 + 1, sum // i + i // 2 + 1)] ) i += 1 return res[::-1]
