前一段时间我有一次有趣的面试经历。这个问题开始很容易：

Q1 ：我们有包含数字的袋子1，2，3，…，
100。每个数字仅出现一次，因此有100个数字。现在，从袋子中随机抽取一个号码。查找丢失的号码。

当然，我之前曾听过这个面试问题，所以我很快按照以下方式回答：

A1 ：好吧，数字的总和1 + 2 + 3 + … + N是(N+1)(N/2)（请参阅Wikipedia：算术级数的总和）。因为N= 100，总和是5050。

因此，如果袋子中所有数字都存在，则总和为5050。由于缺少一个数字，所以总和小于该数字，而差就是那个数字。因此，我们可以找到O(N)时间和O(1)空间上缺少的数字。

在这一点上，我认为我做得不错，但是突然之间，这个问题突然发生了变化：

Q2 ：是的，但是现在如果缺少 两个 数字，您将如何处理？

我之前从未见过/听过/考虑过这种变化，所以我感到惊慌，无法回答这个问题。面试官坚持要了解我的思维过程，所以我提到也许我们可以通过与预期产品进行比较来获得更多信息，或者也许在从第一遍收集到一些信息之后再进行第二遍，等等，但是我真的只是在拍摄在黑暗中，而不是真正找到解决方案的清晰途径。

面试官的确通过说第二个方程式确实是解决问题的一种方式来鼓励我。在这一点上，我有点不高兴（因为事先不知道答案），问我这是否是一种通用的（读作：“有用的”）编程技术，还是仅仅是一个技巧/陷阱。

面试官的回答让我感到惊讶：您可以推广该技术以找到3个缺失的数字。实际上，您可以将其概括以找到 k个 缺失数字。

Qk ：如果袋子中恰好缺少 k个 数字，您将如何有效地找到它？

这是几个月前，但我仍然不知道这种技术是什么。显然存在Ω(N)时间下限，因为我们必须至少扫描一次所有数字，但访问员坚持认为求解技术的 TIME 和
SPACE 复杂度（减去O(N)时间输入扫描）以 k 而非 N 定义。

所以这里的问题很简单：

• 您将如何解决 Q2 ？
• 您将如何解决 Q3 ？
• 您将如何解决 Qk ？

澄清说明

• 通常，从1 .. N开始 有 N个 数字，而不仅仅是1..100。 __
• 我不是在寻找明显的基于集合的解决方案，例如，使用位集，通过指定位的值编码每个数字的存在/不存在，因此使用O(N)其他空间中的位。我们无法承受与 N 成正比的任何额外空间。
• 我也不在寻找明显的排序优先方法。这种方法和基于集合的方法在采访中值得一提（它们易于实现，并且取决于 N ，可能非常实用）。我正在寻找“圣杯”解决方案（可能实现或可能不实际，但仍具有所需的渐近特性）。

因此，当然，您必须再次扫描中的输入O(N)，但是您只能捕获少量信息（用 k 而不是 N 定义），然后必须以某种方式找到 k个 缺失的数字。