[LeetCode]Consecutive Numbers Sum

Brute Force的解法，对于n，我们尝试从1到N开头的所有连续sequence，看是否相加等于N。但显然时间复杂度太高，需要O(n^2)。如果我们从数学的角度分析这道题，假设序列从k + 1开始，一直到k + i的长度为i的序列，我们有等式(2 * k + 1 + i) * i = 2 * N，那么我们可以推导出k = (2 * N - i * (i + 1)) / (2 * i)。i的范围满足i * (i + 1) / 2 <= N，因为从1开始的序列肯定是最长的。由此我们遍历所有的i看能否找到满足等式的非负整数k即可。时间复杂度O(sqrt(n))，代码如下：

	class Solution {
	public:
	int consecutiveNumbersSum(int N) {
	//k + 1 + k + 2 + ... + k + i = (2 * k + 1 + i) * i = 2 * N, k = (2 * N - i * (i + 1)) / 2 * i
	//for max i, 1 + 2 + ... + i = i * (i + 1) / 2 <= N
	//we try all possible is and to see if we can find a k non-negative integer k
	int cnt = 0;
	for(int i = 1; i * (i + 1) <= 2 * N; ++i)
	if ((2 * N - i * (i + 1)) % (2 * i) == 0)++cnt;
	return cnt;
	}
	};

view raw Consecutive Numbers Sum.cpp hosted with ❤ by GitHub