难度: Hard
给定一个正整数 n，返回 连续正整数满足所有数字之和为 n 的组数 。
示例 1:
输入: n = 5 输出: 2 解释: 5 = 2 + 3，共有两组连续整数([5],[2,3])求和后为 5。
示例 2:
输入: n = 9 输出: 3 解释: 9 = 4 + 5 = 2 + 3 + 4
示例 3:
输入: n = 15 输出: 4 解释: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
提示:
1 <= n <= 109运行时间: 51 ms
内存: 16.3 MB
import copy
import collections
class Solution:
def consecutiveNumbersSum(self, n: int) -> int:
prime_factors=collections.defaultdict(int)## 字典用来存储所有质因数，key是质因数，value是质因数的次数
K=2*n
b=2
while b**2<=K:
if not K % b:
prime_factors[b]+=1
K//=b# 若是，则把质数b从K中拿出，保证了后面的b只可能是质数
else:
b+=1
prime_factors[K]+=1 #最后剩下的K是2N的最大质因数
factors = [] ## 列表用来存储所有因数
def traceback(component,prime_factors):
if not prime_factors:
factors.append(component)## 把所有的因数记录下来
else:
dic=copy.deepcopy(prime_factors)
item=dic.popitem()## 从字典里取出一个质因数（一个tuple键值对）
for i in range(item[1]+1):
traceback(component*item[0]**i,dic) ## 对于这个质因数，考虑其在因数中可以出现的次数，最少0次，最多item[1]次
traceback(1,prime_factors)
res=0
for factor in factors:
if factor ** 2<2*n and ((2*n)//factor-factor)%2:
res+=1
return res
这个题解利用了数学和因数分解的方法来解决问题。首先，题解考虑了将输入的 n 扩大两倍至 2*n，并试图分解这个数字的所有因数。解题核心在于分解出所有可能的因数组合，并从中判定那些因数可以通过一个特定的公式来表示连续整数之和等于原始的 n。通过一种深度优先搜索的方式，生成 2*n 的所有因数，然后对这些因数进行检查，看它们是否能形成连续整数序列的和。具体来说，如果某个因数 x 使得 (2*n // x - x) 是奇数，那么这个 x 可以构成一个解。这是因为可以通过解方程组得出连续整数的起点和终点来检查 x 是否为有效因数。
时间复杂度: O(sqrt(K))，其中 K = 2*n
空间复杂度: O(sqrt(K) + log(K))
import copy
import collections
class Solution:
def consecutiveNumbersSum(self, n: int) -> int:
prime_factors = collections.defaultdict(int) # 存储所有质因数
K = 2 * n
b = 2
while b ** 2 <= K:
if not K % b:
prime_factors[b] += 1
K //= b
else:
b += 1
prime_factors[K] += 1 # 最后剩下的K是2N的最大质因数
factors = [] # 存储所有因数
def traceback(component, prime_factors):
if not prime_factors:
factors.append(component) # 记录因数
else:
dic = copy.deepcopy(prime_factors)
item = dic.popitem() # 取出一个质因数
for i in range(item[1] + 1):
traceback(component * item[0] ** i, dic)
traceback(1, prime_factors)
res = 0
for factor in factors:
if factor ** 2 < 2 * n and ((2 * n) // factor - factor) % 2:
res += 1
return res
这个方法基于公式推导的需要。考虑连续整数求和的问题，如果存在k个连续整数之和等于n，则这k个整数可以表示为x, x+1, ..., x+k-1。这个序列的和可以表示为kx + (k*(k-1))/2 = n。为了简化这个方程，并使其易于通过因数分解解决，乘以2以消除分数，得到2kx + k(k-1) = 2n。这样，可以通过将2n因数分解，然后检查这些因数是否能够通过此方程满足条件，来找到所有可能的k和x。
对于连续整数序列和为n的方程kx + k(k-1)/2 = n，我们乘以2并重写为2kx + k(k-1) = 2n。如果我们将x表示为y - (k-1)/2，即x是从y开始向前和向后扩展的中间点，那么这个方程可以简化为k(2y-k+1) = 2n。设x = (2n // k - k + 1) / 2，为了使x为整数，(2n // k - k + 1)必须是偶数，这意味着对于k来说，(2n // k - k)必须是奇数。这种表示方式直接关联了连续序列的起点和整体长度。
使用深度优先搜索（DFS）来生成因数，利用质因数分解的结果来递归地探索所有可能的因数组合，这可以确保生成2*n的所有因数而不遗漏。与直接计算因数（通常需要检查到sqrt(n)）相比，DFS可以在发现质因数后更系统地探索所有因数组合，尤其是在因数分布不均匀时。这种方法更灵活地处理质因数的幂次组合，对于大数的因数分解尤其有效。
条件'factor ** 2 < 2 * n'是为了确保在方程k(2y-k+1) = 2n中，k是一个有效的因数。如果factor ** 2 >= 2 * n，那么当我们将k设置为factor时，2y-k+1将不可能是正整数，因此无法形成有效的连续整数序列。这个条件保证了k和相应的y可以构成一个实际的连续整数序列。