我们可以通过把数字本身和这些数字的平方相加来解Q2。

我们可以把问题简化为

k1 + k2 = x
k1^2 + k2^2 = y

其中x和y表示和低于期望值的程度。

代换给我们:

(x-k2)^2 + k2^2 = y

然后我们可以解出缺失的数。

我不知道这是否有效，但我想建议这个解决方案。

计算这100个元素的xor 计算98个元素的xor(在2个元素被移除之后) 现在(1的结果)XOR(2的结果)给你两个缺失的no的XOR，如果a和b是缺失的元素 4.用常用的求和公式diff得到缺失的no的和，我们设diff是d。

现在运行一个循环，得到可能的对(p,q)，它们都位于[1,100]，和为d。

当获得一对时，检查(3的结果)是否XOR p = q 如果是，我们就完成了。

如果我错了，请纠正我，如果这是正确的，也请评论时间复杂性

我会用另一种方法来回答这个问题，询问面试官关于他试图解决的更大问题的更多细节。根据问题和围绕它的需求，显而易见的基于集的解决方案可能是正确的，而生成一个列表然后从中挑选的方法可能不是。

For example, it might be that the interviewer is going to dispatch n messages and needs to know the k that didn't result in a reply and needs to know it in as little wall clock time as possible after the n-kth reply arrives. Let's also say that the message channel's nature is such that even running at full bore, there's enough time to do some processing between messages without having any impact on how long it takes to produce the end result after the last reply arrives. That time can be put to use inserting some identifying facet of each sent message into a set and deleting it as each corresponding reply arrives. Once the last reply has arrived, the only thing to be done is to remove its identifier from the set, which in typical implementations takes O(log k+1). After that, the set contains the list of k missing elements and there's no additional processing to be done.

这当然不是批处理预先生成的数字袋的最快方法，因为整个过程运行O((log 1 + log 2 +…)+ log n) + (log n + log n-1 +…+ log k))。但它确实适用于任何k值(即使它事先不知道)，在上面的例子中，它的应用方式使最关键的区间最小化。

你可以解出Q2如果你有两个链表的和和和两个链表的乘积。

(l1为原始列表，l2为修改后的列表)

d = sum(l1) - sum(l2)
m = mul(l1) / mul(l2)

我们可以优化它，因为等差级数的和是第一项和最后一项的平均值的n倍:

n = len(l1)
d = (n/2)*(n+1) - sum(l2)

现在我们知道(如果a和b是被移除的数字):

a + b = d
a * b = m

所以我们可以重新排列为:

a = s - b
b * (s - b) = m

然后乘出来:

-b^2 + s*b = m

然后重新排列，使右边为零

-b^2 + s*b - m = 0

然后用二次公式求解:

b = (-s + sqrt(s^2 - (4*-1*-m)))/-2
a = s - b

Python 3示例代码:

from functools import reduce
import operator
import math
x = list(range(1,21))
sx = (len(x)/2)*(len(x)+1)
x.remove(15)
x.remove(5)
mul = lambda l: reduce(operator.mul,l)
s = sx - sum(x)
m = mul(range(1,21)) / mul(x)
b = (-s + math.sqrt(s**2 - (-4*(-m))))/-2
a = s - b
print(a,b) #15,5

我不知道根号，减法和求和函数的复杂性，所以我无法计算出这个解决方案的复杂性(如果有人知道，请在下面评论)。

要解决缺少2(和3)个数字的问题，您可以修改quickselect，它平均在O(n)内运行，如果分区是就地完成的，则使用恒定内存。

Partition the set with respect to a random pivot p into partitions l, which contain numbers smaller than the pivot, and r, which contain numbers greater than the pivot. Determine which partitions the 2 missing numbers are in by comparing the pivot value to the size of each partition (p - 1 - count(l) = count of missing numbers in l and n - count(r) - p = count of missing numbers in r) a) If each partition is missing one number, then use the difference of sums approach to find each missing number. (1 + 2 + ... + (p-1)) - sum(l) = missing #1 and ((p+1) + (p+2) ... + n) - sum(r) = missing #2 b) If one partition is missing both numbers and the partition is empty, then the missing numbers are either (p-1,p-2) or (p+1,p+2) depending on which partition is missing the numbers. If one partition is missing 2 numbers but is not empty, then recurse onto that partiton.

由于只缺少2个数字，该算法总是丢弃至少一个分区，因此保持了O(n)个快速选择的平均时间复杂度。类似地，当缺少3个数字时，该算法也会在每次传递中丢弃至少一个分区(因为当缺少2个数字时，最多只有1个分区包含多个缺少的数字)。然而，我不确定当添加更多缺失的数字时，性能会下降多少。

下面是一个不使用就地分区的实现，所以这个例子不满足空间要求，但它确实说明了算法的步骤:

<?php

  $list = range(1,100);
  unset($list[3]);
  unset($list[31]);

  findMissing($list,1,100);

  function findMissing($list, $min, $max) {
    if(empty($list)) {
      print_r(range($min, $max));
      return;
    }

    $l = $r = [];
    $pivot = array_pop($list);

    foreach($list as $number) {
      if($number < $pivot) {
        $l[] = $number;
      }
      else {
        $r[] = $number;
      }
    }

    if(count($l) == $pivot - $min - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($min, $pivot-1)) - array_sum($l) . "\n";
    }
    else if(count($l) < $pivot - $min) {
      // more than 1 missing number, recurse
      findMissing($l, $min, $pivot-1);
    }

    if(count($r) == $max - $pivot - 1) {
      // only 1 missing number use difference of sums
      print array_sum(range($pivot + 1, $max)) - array_sum($r) . "\n";
    } else if(count($r) < $max - $pivot) {
      // mroe than 1 missing number recurse
      findMissing($r, $pivot+1, $max);
    }
  }

Demo

试着找出从1到50的数的乘积:

令product, P1 = 1 × 2 × 3 × .............50

当你一个一个地把数提出来，把它们相乘，就得到乘积P2。但是这里少了两个数字，因此P2 < P1。

这两项的乘积，a x b = P1 - P2。

你已经知道这个和了，a + b = S1。

由上述两个方程，用二次方程求解a和b。A和b是你缺失的数。