题目描述

给定一个正整数 N,试求有多少组连续正整数满足所有数字之和为 N

示例 1:
输入: 5
输出: 2
解释: 5 = 5 = 2 + 3,共有两组连续整数([5],[2,3])求和后为 5。

示例 2:
输入: 9
输出: 3
解释: 9 = 9 = 4 + 5 = 2 + 3 + 4

示例 3:
输入: 15
输出: 4
解释: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

说明: $1 \leq N \leq 10^9$

解题思路

最开始直接考虑暴力求解,但是暴力求解的时间复杂度为 $O(n^2)$。
下面开始寻找规律,看看能不能从数据中找到一些算法。
题目中要求我们去寻找连续正整数,也就是说最后的求和序列的前后两项之差一定为1。即:
$$a_n - a_{n-1} = 1$$
我们可以根据高中学过的等差数列的有关知识,得到下面的式子:
$$N = \frac{1}{2}(a_1 + a_n)$$
其中$N$是求和最终的结果,也就是输入的值;$a_1$是首项,也就是序列开始的值,如示例1中的5和2;$a_n$是末项,并且我们知道$a_n=a_1+i-1$,其中$i$代表第$i$项。下面为了方便,我们令$a=a_1$。
于是,$N$可以被重新改写为:
$$N = \frac{1}{2}(a+a+i-1)$$
等价于:
$$
a = \frac{N}{i} - \frac{i-1}{2};(a>0)
$$
根据$a>0$的条件:
$$
\frac{N}{i} - \frac{i-1}{2} > 0
$$
不妨令:
$$
\frac{N}{i} - \frac{i-1}{2} = 0
$$
显然这个方程有解,解得:
$$
i_{\pm} = \frac{1}{2} \pm \sqrt{2N+\frac{1}{4}}
$$
又因为 $i>0$,所以我们最终求取的$i$的所有可能值的范围一定是$(0,i_{+})$中的所有满足a为正整数的整数。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int consecutiveNumbersSum(int N) {
int result = 0;
double end = 0.5 + sqrt(N*2 + 0.25);
double i = 1;
while(i < end){
double a = N / i - (i - 1) /2;
if(a == floor(a)){
result ++;
}
i++;
}
return result;
}
};

代码中的$end$即推导过程中的$i_+$。

其他

其实我最开始是用的 JavaScript 来写的这道题,然后代码里面全都是用的 var,后来用 C++ 重写的时候,全部替换成 int,然后因为类型转换的问题结果出了问题,懵逼了半天。。(我怎么这么菜。。。

JavaScript代码如下:

1
2
3
4
5
6
7
8
9
10
var consecutiveNumbersSum = function(N) {
var result = 0;
var end = 0.5 + Math.sqrt(2*N + 0.25);
for(var i = 1; i < end; i++){
var a = N / i - (i - 1) / 2;
if(a === Math.floor(a))
num++;
}
return num;
};

这道题最开始我是想的用DP,就像整数分解成若干项之和的题一样,后来发现这道题的规律很明显。(然而我高中数学都忘光了。。