题目描述：

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: 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，将其表示为若干连续整数之和。求可以找到多少种这样的组合。

解题思路：

枚举连续整数的个数c

当c为奇数时， floor(N / c) 为第(c + 1) / 2个数

当c为偶数时，floor(N / c)为第c / 2个数

综上，floor(N / c)为第c / 2 + c % 2个数，并且floor(N / c) ≥ c / 2 + c % 2

c符合下列两种情况时，存在一组长度为c的连续整数和为N

c为奇数，并且N可以整除c

c为偶数，并且floor(N / c) * c + c / 2 == N

Python代码：

class Solution(object):
    def consecutiveNumbersSum(self, N):
        """
        :type N: int
        :rtype: int
        """
        ans = c = 0
        while True:
            c += 1
            if N / c < c / 2 + c % 2:
                break
            if c % 2 and N % c == 0:
                ans += 1
            elif c % 2 == 0 and (N / c) * c + c / 2 == N:
                ans += 1
        return ans

 

本文链接：http://bookshadow.com/weblog/2018/05/06/leetcode-consecutive-numbers-sum/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码