在数组中查找连续范围

我认为以下解决方案将在O（n）时间中使用O（n）空间工作。

首先将数组中的所有条目放入哈希表。接下来，创建第二个哈希表，该表存储我们已“访问”的元素，该元素最初为空。

现在，一次遍历元素数组。对于每个元素，检查该元素是否在访问集中。如果是这样，请跳过它。否则，从该元素开始向上计数。在每个步骤中，检查当前数字是否在主哈希表中。如果是这样，请继续，并将当前值标记为已访问集的一部分。如果没有，请停止。接下来，重复此过程，除了向下计数。这告诉我们包含此特定数组值的范围内的连续元素数。如果我们跟踪以这种方式找到的最大范围，我们将有一个解决方案。

该算法的运行时复杂度为O（n）。要看到这一点，请注意，我们可以在O（n）时间的第一步中构建哈希表。接下来，当我们开始扫描到数组以找到最大范围时，每个扫描范围所花费的时间与该范围的长度成比例。由于范围长度的总和是原始数组中元素的数量，并且由于我们从未两次扫描相同的范围（因为我们标记了我们访问的每个数字），因此第二步将O（n）时间作为好，对于O（n）的净运行时间。

编辑： 如果您很好奇，我可以使用该算法的
Java实现
，以及对其工作原理以及运行时正确性的详细分析。它还探讨了一些在算法的初始描述中不明显的边缘情况（例如，如何处理整数溢出）。

希望这可以帮助！