[LeetCode] 829. Consecutive Numbers Sum

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)