LeetCode829-连续整数求和

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/consecutive-numbers-sum/

中文链接：https://leetcode-cn.com/problems/consecutive-numbers-sum/

题目详述

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

示例 1:

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

示例 2:

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

示例 3:

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

说明: 1 <= N <= 10 ^ 9

题目详解

  • 实际上就是求公差为 1 的等差数列各个元素之和为 N 的数列有多少个。
  • 设首项为 a，有 b 项，则和为 (a + a + b - 1) b / 2。(a + a + b - 1) b / 2 = N 等价于 a = (2 * N / b - (b - 1)) / 2。要使条件满足，则要满足以下要求：
  • 1.所有除法都是整除。这意味着 b 是 2N 的约数，2 能整除 2 N / b - (b - 1)。
  • 2.a > 0。这意味着 2 N > b (b - 1)。
  • 统计满足上述条件的数列有多少个即可。
1
2
3
4
5
6
7
8
9
10
11
12
public class LeetCode_00829 {

    public int consecutiveNumbersSum(int N) {
        int res = 0;
        for (int b = 1; b * (b - 1) < 2 * N; ++b) {
            if (2 * N % b == 0 && (2 * N / b - (b - 1)) % 2 == 0) {
                ++res;
            }
        }
        return res;
    }
}
  • 我们也可以运用等差数列的另一个求和公式，设首项为 a，有 k 项，则和为 k a + k (k - 1) / 2。
  • 同理，求满足 k a + k (k - 1) / 2 = N 的数列有多少个即可。
1
2
3
4
5
6
7
8
9
10
11
12
public class LeetCode_00829 {

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