我们得到N（3 <= N <= 50000）张牌，唯一编号从1到N。我们丢失了大约3张卡，我们的目标是找到它们。
输入：第一行包含卡数 N。第二行包含 3 个数字：我们拥有的所有剩余卡片的总和、它们的平方和它们的立方体之和。
输出：3张丢失的卡的数量，按任意顺序排列。
这是我尝试的：我为丢失的卡找到了相同的 3 个总和，然后检查可能的数字，直到其中三个满足我们的总和。
有没有更快的解决方案？我必须在 Python 中通过 2 秒的时间限制，最大 N = 50000。
N = int(input())
lst = list(range(1, N+1))
s_rest, s2_rest, s3_rest = list(map(int, input().split()))
s = sum(lst)
s2 = sum([x**2 for x in lst])
s3 = sum([x**3 for x in lst])
# sums of 3 lost numbers
s_lost = s - s_rest
s2_lost = s2 - s2_rest
s3_lost = s3 - s3_rest
def find_numbers():
"""Find first appropriate option"""
for num1 in range(s_lost):
for num2 in range(s_lost):
for num3 in range(s_lost):
if (num1 + num2 + num3 == s_lost) and (num1**2 + num2**2 + num3**2 == s2_lost)
and (num1**3 + num2**3 + num3**3 == s3_lost):
return (num1, num2, num3)
answer = find_numbers()
print(answer[0], answer[1], answer[2])
例子
输入：
四
11 1
输出：
2 3 4
输入：
5
6 26 126
输出：
2 3 4
如果你的未知数是x，y，z，那么你有一个由三个方程组成的系统。
x + y + z = a //your s_lost
x^2 + y^2 + z^2 = b //your s2_lost
x^3 + y^3 + z^3 = c //your s3_lost
虽然这个系统的直接解决方案似乎太复杂了，但我们可以修复一个未知的系统并解决更简单的系统。例如，检查 z 的所有可能值并求解 x 和 y 的系统
for z in range(s_lost):
....
现在让我们看看新系统：
x + y = a - z = aa
x^2 + y^2 = b - z^2 = bb
substitute
x = aa - y
(aa - y)^2 + y^2 = bb
2 * y^2 - 2 * y * aa - bb + aa^2 = 0
solve this quadratic equation for y
D = 4 * aa^2 - 8 * (aa^2 - bb) = 8 * bb -4 * aa^2
y(1,2) = (2*aa +- Sqrt(D)) / 4
因此，对于每个 z 值查找：
- 解是否给出 y
的整数值- 然后得到X
- 然后检查立方和方程是否为真。
使用这种方法，您将获得线性复杂度 O（N） 与立方复杂度 O（N^3） 的解。
附言如果方程组的简单数学解确实存在，则其复杂度为O（1））
这可以通过数学方法简化。你得到 3 个方程，有 3 个未知数。
sum(1+2+..+N) - x1 - x2 - x3 = a
sum(1^2+2^2+..+N^2) - x1^2 - x2^2 - x3^3 = b
sum(1^3+2^3+..+N^3) - x1^3 - x2^3 - x3^3 = c
显然sum(1..N)是1/2 *N(N+1)，而sum(1^2+2^2+3^2+..+N^2)是1/6 *N*(N+1)*(2N+1)的，sum(1^3+2^3+..+N^3)可以写成1/4 *N^2 *(N+1)^2。以下是 wolframalpha 输出： ∑k， ∑k^2， ∑k^3
在这一点上，剩下的事情就是求解给定的方程组（3 个未知数是完全可以解决的）并实现它。您只需要找到一个解决方案，使其更加容易。运行时间为 O（1）。
肯定有更快的方法！
对于 N=50,000，您的蛮力函数必须弥补
N * N * N = 125,000,000,000,000
迭代，所以这不是一个选项。
此外，您应该检查num1 == num2等以避免重复的数字（问题没有明确说明，但我知道"我们丢失了大约 3 张牌"意味着您需要找到满足给定条件的三个不同的数字）。
您可以对列表进行排序，并找到a[i+1] =/= a[i]+1的对。对于每个这样的对，[a[i]+1;a[i+1])数字都丢失了。这将为您提供 O（n log n） 运行时间。
我可以给你一个想法，
让sum1 = 1+2+3...n
让sum2 = 1^2+2^2+3^2...n
p, q, r是连续输入给出的三个数字。
我们需要搜索a, b, c.迭代for c = 1 to N.
对于每次迭代，
让x = sum1 - (p+c)
让y = sum2 - (q+c*c)
如此a+b = x和a^2+b^2 = y.
自a^2+b^2 = (a+b)^2 - 2ab以来，你可以从方程a^2+b^2 = y中找到2ab。
a+b已知并且已知ab，通过一点数学计算，您可以找到是否存在a和b的解（它形成二次方程）。如果存在，请打印解决方案并中断迭代。
这是一个O(N)解决方案。