829. Consecutive Numbers Sum

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?

Example 1:

Input: 5
Output: 2
Explanation: 5 = 5 = 2 + 3

Example 2:

Input: 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4

Example 3:

Input: 15
Output: 4
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

Note: 1 <= N <= 10 ^ 9.

这道题给了一个正整数N,问N能写成多少种连续正整数之和,比如9可以写成 4+5,或者 2+3+4。这道题其实不好做,因为没有固定的算法可以套,而更多的考察是数学知识,而且比较难想。由于要写成连续正整数之和,则肯定是一个等差数列,并且差值为1,这个等差数列不必从1开始,假设其是从x开始的,且个数共有k个,则可以写出这个等差数列为:

x, x+1, x+2, ..., x+k-1

其和为N,根据等差数列的求和公式,可以写出下列等式:

kx + (k-1)k / 2 = N

变形后可得到:

kx = N - (k-1)k / 2

这样,只要对于任意一个k值,x能得到正整数解,就表示一定会有一个对应的等差数列和为N。下面要来求k的范围,由于k是等差数列的长度,首先肯定是要大于0的,这是下限。求上限还是要利用上面的那个式子,由于x也必须是正整数,可以得到不等式:

N - (k-1)k / 2 > 0

从而得到近似解:

k < sqrt(2N)

有了k的范围就可以开始遍历了,首先数字N本身也是符合题意的,可以看作是长度为1的等差数列,则 res 可以初始化为1,然后i从2遍历到 sqrt(2N),对于每个i值,只要 (N - i(i-1)/2) 能整除i,就表示存在长度为i的等差数列和为N,结果 res 自增1,这样就可以求出所有符合题意的等差数列的个数,参见代码如下:

解法一:

class Solution {
public:
    int consecutiveNumbersSum(int N) {
        int res = 1;
        for (int i = 2; i < sqrt(2 * N); ++i) {
            if ((N - i * (i - 1) / 2) % i == 0) ++res;
        }
        return res;
    }
};

还可以换一种写法,核心思路还是跟上面的解法相同,要找是否存在和为N的等差数列,根据上面的分析,需要看等差数列的起始值x是否为整数,若这个等差数列每个数字都减去一个 x-1,就变成了一个从1开始的差值为1的等差数列,那就让i从1开始遍历,用一个变量 sum,每次都加上i值,这样就相当于计算了这个等差数列的和,然后每次看 N-sum 是否能整除i,能的话就表明存在长度为i的等差数列和为N,参见代码如下:
解法二:

class Solution {
public:
    int consecutiveNumbersSum(int N) {
        int res = 0, sum = 0;
        for (int i = 1; sum < N; ++i) {
            sum += i;
            if ((N - sum) % i == 0) ++res;
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/829

参考资料:

https://leetcode.com/problems/consecutive-numbers-sum/

https://leetcode.com/problems/consecutive-numbers-sum/discuss/129227/JAVA-easy-4-lines-O(n0.5)

https://leetcode.com/problems/consecutive-numbers-sum/discuss/128959/5-line-O(N-0.5)-Java-code-Math-method

https://leetcode.com/problems/consecutive-numbers-sum/discuss/129015/5-lines-C%2B%2B-solution-with-detailed-mathematical-explanation.

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

×

Help us with donation