给定n个正实数,任务是对以下问题提供"是"或"否"答案:"是否存在一对数字x和y,使得1 <= x + y <= 2.
显而易见的解决方案是对所有需要O(nlogn)的数字进行排序.现在,可以在O(n)时间内检查对.
然而,预计该问题将在恒定的空间和线性时间内得到解决.任何见解？
只有 0 到 2 之间的数字才有利于参与获胜对。其他的可以忽略。
\n\n每个这样的数字都x可以与1-x和之间的列表中的一个附加数字创建一对2-x。\n在列表中进行时计算并维护可接受的界限。在任何给定时间，可接受的下一个值的间隔不能超过两个，因为所有可接受的下一个值的间隔都包含在 -1 和 2 之间，并且宽度为 1。因此，完成一对的可接受的下一个值可以用常量表示空间。
一旦列表中出现的数字位于可接受的下一个值的最多两个间隔之一中，请立即回答“是”。如果您到达列表末尾而没有遇到这种情况，请回答“否”。
\n\n示例：0.1、0.5、2.0 \xe2\x80\xa6
\n\n开始时，可以出现并完成一对的值集是空集。
读取 0.1 后，如果现在出现的话，将完成一对的值集是 [0.9, 1.9]。
0.5 不属于可以完成一对的值集合。然而，读完后，[0.5,1.5]中的值可以完成一对。由于我们已经有了集合 [0.9, 1.9]，因此可以完成一对的新值集合是 [0.5, 1.9]。
2.0 不属于可以完成一对的值集合。然而，我们现在可以读取 [-1, 0] 中的任何值来完成一对。今后可以读取以完成一对的新值集是 [-1, 0] \xe2\x88\xaa [0.5, 1.9]。
依此类推\xe2\x80\xa6\n