(leetcode)连续整数求和-题解

题目描述

给定一个正整数 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,就像整数分解成若干项之和的题一样,后来发现这道题的规律很明显。(然而我高中数学都忘光了。。

凸包问题 (leetcode)环形链表Ⅱ-题解

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×