算法题连续整数求和-开发者社区

829. 连续整数求和

问题描述

给定一个正整数n，返回可以表示为连续正整数之和的方案数。

示例：

输入:n=5输出:2解释:5=2+3，共2种表示方法（包括5本身）

输入:n=9输出:3解释:9=9=4+5=2+3+4，共3种表示方法

输入:n=15输出:4解释:15=15=7+8=4+5+6=1+2+3+4+5，共4种表示方法

算法思路

数学推导：

数学建模：
- 连续整数从a开始，共k个数：a + (a+1) + (a+2) + ... + (a+k-1) = n
- 等差数列求和公式：k*a + k*(k-1)/2 = n
- 整理：a = (n - k*(k-1)/2) / k
- 要求a为正整数，即(n - k*(k-1)/2) > 0且能被k整除
关键：
- 从公式n = k*a + k*(k-1)/2得2n = k*(2a + k - 1)
- m = 2a + k - 1，则2n = k*m
- 由于a ≥ 1，所以m = 2a + k - 1 ≥ k + 1，即m > k
- k和m的奇偶性不同（因为m - k = 2a - 1是奇数）
方法：
- 方法一：直接枚举长度k，验证是否存在合法的起始值a
- 方法二：计算n的奇数因子个数

代码实现

方法一：枚举连续序列长度

classSolution{/** * 计算正整数n表示为连续正整数之和的方案数 * 通过枚举连续序列的长度k * * @param n 正整数 * @return 表示方案数 */publicintconsecutiveNumbersSum(intn){intcount=0;// k表示连续整数的个数，从1开始枚举// 条件：k*(k+1)/2 <= n，k的最大值约为sqrt(2n)for(intk=1;k*(k+1)/2<=n;k++){// n = k*a + k*(k-1)/2// a = (n - k*(k-1)/2) / kintnumerator=n-k*(k-1)/2;// 检查是否能整除且结果为正整数if(numerator>0&&numerator%k==0){count++;}}returncount;}}

方法二：奇数因子计数

classSolution{/** * 通过计算n的奇数因子个数来求解 * 数学结论：n表示为连续正整数之和的方案数等于n的奇数因子个数 * * @param n 正整数 * @return 表示方案数 */publicintconsecutiveNumbersSum(intn){// 移除所有的因子2，得到奇数部分while(n%2==0){n/=2;}intcount=1;// 至少有因子1// 枚举奇数因子，从3开始for(inti=3;i*i<=n;i+=2){intexponent=0;// 计算当前奇数因子的指数while(n%i==0){exponent++;n/=i;}// 因子个数公式：(e1+1)*(e2+1)*...count*=(exponent+1);}// 如果n > 1，说明还有一个大于sqrt(原n)的奇数质因子if(n>1){count*=2;}returncount;}}

算法分析

时间复杂度：O(√n)
- k的最大值满足k*(k+1)/2 ≤ n，k ≈ √(2n)
空间复杂度：O(1)
- 只使用常数额外空间

算法过程

输入：n = 15

方法一：

k = 1：numerator = 15 - 0 = 15，15 % 1 == 0→a = 15→[15]
k = 2：numerator = 15 - 1 = 14，14 % 2 == 0→a = 7→[7,8]
k = 3：numerator = 15 - 3 = 12，12 % 3 == 0→a = 4→[4,5,6]
k = 4：numerator = 15 - 6 = 9，9 % 4 != 0
k = 5：numerator = 15 - 10 = 5，5 % 5 == 0→a = 1→[1,2,3,4,5]
k = 6：6*7/2 = 21 > 15，停止

结果：4种方案

方法二：

移除因子2：15是奇数，保持不变
质因数分解：15 = 3¹ × 5¹
奇数因子个数：(1+1) × (1+1) = 4
奇数因子：1, 3, 5, 15

结果：4个奇数因子 → 4种方案

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：n = 5System.out.println("Test 1 (n=5): "+solution.consecutiveNumbersSum(5));// 2// 测试用例2：n = 9System.out.println("Test 2 (n=9): "+solution.consecutiveNumbersSum(9));// 3// 测试用例3：n = 15System.out.println("Test 3 (n=15): "+solution.consecutiveNumbersSum(15));// 4// 测试用例4：n = 1（边界情况）System.out.println("Test 4 (n=1): "+solution.consecutiveNumbersSum(1));// 1// 测试用例5：n = 2（2的幂）System.out.println("Test 5 (n=2): "+solution.consecutiveNumbersSum(2));// 1// 测试用例6：n = 8（2的幂）System.out.println("Test 6 (n=8): "+solution.consecutiveNumbersSum(8));// 1// 测试用例7：n = 3System.out.println("Test 7 (n=3): "+solution.consecutiveNumbersSum(3));// 2// 测试用例8：n = 25System.out.println("Test 8 (n=25): "+solution.consecutiveNumbersSum(25));// 3// 25 = 25 = 12+13 = 3+4+5+6+7// 测试用例9：大数测试System.out.println("Test 9 (n=100): "+solution.consecutiveNumbersSum(100));// 3}