连续整数求和

2829. 连续整数求和

给定一个正整数 n，返回连续正整数满足所有数字之和为 n 的组数 。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

1 <= n <= 109

解题思路

若存在某个连续段和为n，由等差数列公式可知，若首项为a，项数为k
$$
\frac{(a+a+k-1)*k}{2}=n
$$

即
$$
(2a+k-1)*k=2n \Rightarrow 2a=\frac{2n}{k}
$$
根据a和k都是正整数可知
$$
2a=\frac{2n}{k}-k+1\geq2 \Rightarrow \frac{2n}{k}\geq k+1\Rightarrow \frac{2n}{k}>k
$$

综上，根据（2）和（3）可知，k一定是2n的约数，且k的取值范围是$[1,\sqrt2n)$，因此我们在这个范围内枚举，如果 k 为 2n 约数，并且结合$2a=\frac{2n}{k}-k+1$验证a，就可以找到一组（a，k）满足连续和为n的解

代码

class Solution {
    public int consecutiveNumbersSum(int n) {
        int ans = 0 ;
        for(int k = 1; k < Math.sqrt(2*n); k++){
            if( (2*n)%k != 0) continue; //k不为2n的约数
            if( ((2*n)/k - k + 1)%2 ==0 ) ans++; //a满足条件
        }
        return ans;
    }
}