问题: 在O(n)的时间复杂度内找到一个数字K，使得1,2,3...K的总和恰好是1,2,3...N总和的一半。
数学: 我知道序列1,2,3....N的总和为N(N+1)/2。
因此，我们的任务是找到一个K，使得： K(K+1) = 1/2 * (N)(N+1)/2，如果存在这样的K。
伪代码:
sum1 = n(n+1)/2
sum2 = 0
for(i=1;i<n;i++)
{
sum2 += i;
if(sum2 == sum1)
{
index = i
break;
}
}
问题：目前解决方案的时间复杂度为O(n)，但我需要更好的解决方案，比如O(n)，O(log(n))...
您的方程式接近正确，但是您在K方面省略了除以2。实际上，您需要
K * (K + 1) / 2 = N * (N + 1) / (2 * 2)
或者
2 * K * (K + 1) = N * (N + 1)
将这个值代入 Wolfram Alpha 中可以得到实数解：
K = 1/2 * (-sqrt(2N^2 + 2N + 1) - 1)
K = 1/2 * (sqrt(2N^2 + 2N + 1) - 1)
由于您可能不想要负值，所以第二个方程是您要寻找的。这应该是一个O（1）的解决方案。
k * (k + 1) = n * (n + 1) / 2 其中n已知然而，问题是OP需要k为整数，但并非每个选定的n都存在这样的值。
sum_n = n * (n + 1) / 2
k = n
repeat indefinitely // It usually needs only a few iterations, it's O(log(n))
f_k = k * (k + 1)
if f_k == sum_n
k is the solution, exit
if f_k < sum_n
there's no k, exit
k_n = (f_k - sum_n) / (2 * k + 1) // Newton step: f(k)/f'(k)
if k_n == 0
k_n = 1 // Avoid inifinite loop
k = k - k_n;
n = 1 // This algorithm compares 2 * k * (k + 1) and n * (n + 1)
sum_n = 1 // It finds all the pairs (n, k) where 0 < n ≤ N in O(N)
sum_2k = 1
for every n <= N // Note that n / k → sqrt(2) when n → ∞
while sum_n < sum_2k
n = n + 1 // This inner loop requires a couple of iterations,
sum_n = sum_n + n // at most.
if ( sum_n == sum_2k )
print n and k
k = k + 1
sum_2k = sum_2k + 2 * k
N K K * (K + 1)
----------------------------------------------
3 2 6
20 14 210
119 84 7140
696 492 242556
4059 2870 8239770
23660 16730 279909630
137903 97512 9508687656
803760 568344 323015470680
4684659 3312554 10973017315470
27304196 19306982 372759573255306
159140519 112529340 12662852473364940
xi+1 = xi + 2yi yi+1 = yi + xi请注意，我们需要“跳过”偶数的y，因为它们会导致非整数解。因此我们可以直接使用这些解。 $x_{i+2} = 3x_i + 4y_i$ 可以翻译为 $u_{i+1} = 3u_i + 4v_i - 3$，$n_{i+1} = 3n_i + 4k_i + 3$； $y_{i+2} = 2x_i + 3y_i$ 可以翻译为 $v_{i+1} = 2u_i + 3v_i - 2$，$k_{i+1} = 2n_i + 3k_i + 2$。
n k
-----------------------------------------------
3* 0 + 4* 0 + 3 = 3 2* 0 + 3* 0 + 2 = 2
3* 3 + 4* 2 + 3 = 20 2* 3 + 3* 2 + 2 = 14
3*20 + 4*14 + 3 = 119 2*20 + 3*14 + 2 = 84
...
看起来这个问题要求解决丢番图方程。
2K(K+1) = N(N+1).
通过检查，K=2，N=3 是一个解决方案！
你所面临的条件是1到N的和是1到K的两倍
因此，你有N(N+1) = 2K(K+1)或K^2 + K - (N^2 + N) / 2 = 0
这意味着K = (-1 +/- sqrt(1 + 2(N^2 + N)))/2
这是O(1)
K存在是一个正确的解决方案（而不仅仅是四舍五入）。 - scohe001
K(K+1) = 1/2 * (N)(N+1)/2关于K的方程，然后你就能在常数时间内得到结果。 - 463035818_is_not_a_number