LeetCode 829. 连续整数求和（数学）

Michael阿明

发布于 2020-07-13 16:31:17

1.2K0

发布于 2020-07-13 16:31:17

1. 题目

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

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

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

示例 3:
输入: 15
输出: 4
解释: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
说明: 1 <= N <= 10 ^ 9

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/consecutive-numbers-sum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

设长度为n，首项为a 则

a*n+n*(n-1)/2 = N

a = \frac{2N-n(n-1)}{2n}

, 且分子需要大于0

n^2+(2a-1)n=2N

, 则 n 最大取

\sqrt{2N}

class Solution {
public:
    int consecutiveNumbersSum(int N) {
        //a0 = (2*N-n*(n-1))/(2*n) , n为长度
        int M = ceil(sqrt(2*N)), count = 0, up;
    	for(int n = 1; n <= M; ++n)
    	{
    		up = (N<<1)-n*(n-1);
    		if(up > 0 && (up%(n<<1) == 0))
    			++count;
    	}
    	return count;
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-12-12 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度

LeetCode 829. 连续整数求和（数学）

LeetCode 829. 连续整数求和（数学）

1. 题目

2. 解题

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐