題目連結
2 pointers 小範圍可以做，只是這題範圍太大…
那轉用數學吧！
假設某一種合法的答案為 $$N = (s+1) + (s+2) + (s+3) + … + (s+k)$$
那我們可以推得 $$N = s*k + \frac{(1 + k) * k}{2}$$ $$2N = k(2s + k + 1)$$
我們可以觀察到 $2N > k$，進一步觀察右邊其實有 $k^2$，所以其實我們的搜尋範圍只有 $2N > k^2$
AC Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#ifdef LOCAL
#include <bits/stdc++.h>
using namespace std;
// tree node stuff here...
#endif
static int __initialSetup = []()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}
();
class Solution
{
public:
int consecutiveNumbersSum(int N)
{
int ans = 0;
for (int k = 1; k * k < 2 * N; k++) {
if (2 * N % k != 0)
continue;
if ((2 * N / k - k - 1) % 2 == 0) {
int s = (2 * N / k - k - 1) / 2;
// cout << "s " << s + 1 << endl;
if (k * (2 * s + k + 1) == 2 * N)
ans++;
}
}
return ans;
}
};
#ifdef LOCAL
int main()
{
cout << Solution().consecutiveNumbersSum(5) << endl;
return 0;
}
#endif
|