LeetCode-829. Consecutive Numbers Sum

LeetCode-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: 5Output: 2Explanation: 5 = 5 = 2 + 3

Example 2:

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

Example 3:

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

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

题解：

本题使用左右指针滑动窗口的话超时，有个O(n^0.5)解法：

假设有k个连续的数字，它们的和为N。最小的k个连续的数字之和是1 + 2 + 3 + … + k。从1开始的连续k个数字之和不一定等于N。可能存在一个整数i，(i + 1) + (i + 2) + (i + 3) + … + (i + k) = N。我们把这个等式稍微变换一下就有1 + 2 + 3 + … + k + i × k = N，也就是N - (1 + 2 + 3 + … + k) = i × k。

这个公式告诉我们，如果有k个连续的数字的和等于N，那么一定存在一个整数i，N 减去1 + 2 + 3 + … + k的差等于i × k。也就是说N减去1 + 2 + 3 + … + k的差一定能被k整除。

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。