829.Consecutive Numbers Sum
829.Consecutive numbers sum
题目难度 Medium
给定一个正整数 N,试求有多少组连续正整数满足所有数字之和为 N?
1
示例 1:
2
输入: 5
3
输出: 2
4
解释: 5 = 5 = 2 + 3,共有两组连续整数([5],[2,3])求和后为 5。
5
示例 2:
6
输入: 9
7
输出: 3
8
解释: 9 = 9 = 4 + 5 = 2 + 3 + 4
9
示例 3:
10
输入: 15
11
输出: 4
12
解释: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
13
说明: 1 <= N <= 10 ^ 9
Copied!
需要注意的是,当N比较大时,因为int类型的表达范围,sqrt计算根时会丢失数据,如8*N则可改为8.0*N转换为float或者double。 最初方法一: 根据等差数列求和公式,对于首项x1计算出项数n,然后通过求和比较是否和为N,x1从1循环到N,但这种方式只适用于N比较小的情况,Leetcode这题会显示超时。
1
class Solution {
2
public:
3
int consecutiveNumbersSum(int N) {
4
int num=0;
5
for(int i=1;i<=N;i++)
6
{
7
int n= (sqrt((2.0*i-1)*(2*i-1)+8*N)- 2*i +1)/2 ;
8
if(n>0 && n*(i+i+n-1) == 2*N)
9
num++;
10
}
11
return num;
12
13
}
14
};
Copied!
方法二:通过循环n来求出x1,因为n的数目不可能超过从1+..+xn=N中的xn,因此求出最大项数maxnum。然后同样用求和公式求出x1,最后进行求和比较,判断是否满足条件。测试时长:8ms
1
class Solution {
2
public:
3
int consecutiveNumbersSum(int N) {
4
int num=1;
5
int maxnum= (sqrt(N*8.0+1)-1)/2;
6
for(int n=2;n<=maxnum;n++)
7
{
8
int x1 = ((2*N)/n -n+1)/2;
9
10
if(n*(x1*2+n-1) == 2*N)
11
{
12
num++;
13
//printf("%d\t%d\n",x1,n);
14
}
15
}
16
return num;
17
18
}
19
};
Copied!
Copy link