连续整数求和
Consecutive Numbers Sum
题目详情
问题：连续整数求和
考察：数组
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/consecutive-numbers-sum/
Given an integer n, return the number of ways you can write n as the sum of consecutive positive integers.
Example 1:
Input: n = 5 Output: 2 Explanation: 5 = 2 + 3
Example 2:
Input: n = 9 Output: 3 Explanation: 9 = 4 + 5 = 2 + 3 + 4
Example 3:
Input: n = 15 Output: 4 Explanation: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5
Constraints:
1 <= n <= 109
解析
思路：设 N 表示为 k 个连续正整数，首项 a 满足 N = k(2a+k-1)/2。枚举长度 k，只要 N - k(k-1)/2 能被 k 整除且首项为正，就是一种表示。
复杂度：枚举到 k(k+1)/2 <= N，时间 O(sqrt(N))，空间 O(1)。