其范围之和（1,2）的三元组

Question

给定n数组中的正实数，找出该集合中是否 存在 三元组，使得三元组的总和在范围内(1, 2)。在线性时间和恒定空间中进行。

• 数组未排序。
• 数字为正
• 数字是 实数
  
  

任何帮助将不胜感激。谢谢。

Answer 1

诀窍是找出一种方法，对可能的解决方案进行分类，并为每个解决方案提出一个线性时间恒定空间解决方案。

考虑这三个范围X = (0,2/3), Y = [2/3,1], Z = (1,2)。最多可以有一个值Z（如果有两个值来自Z，则总和将超过1+1=2）。同样，至少一个值必须来自X。假设有3个值，a <= b <= c因此1 <= a+b+c <= 2。然后，考虑哪些可行的解决方案类别是可行的：

A) `a \in X, b \in X, C \in X` 
B) `a \in X, b \in X, C \in Y` 
C) `a \in X, b \in X, C \in Z` 
D) `a \in X, b \in Y, C \in Y` 
E) `a \in X, b \in Y, C \in Z`

那么我们如何测试每种情况？

案例A非常容易测试：保证总和小于2，因此我们只需要测试最大和（X中最大的3个元素）超过1。

情况C非常容易测试：由于保证了总和大于1，我们只需要检查总和是否小于2。因此，为了做到这一点，我们只需要测试X中的最小2个值即可。 Z的最小值

情况D和E与C相似（因为总和必须至少为4/3> 1，因此请在每个类别中选择最小的值）。

情况B是唯一棘手的情况。 0 < a+b < 4/3和2/3 <= c <= 1。为了处理情况B，我们考虑以下间隔：X1 =（0，1/2），X2 =
[1/2 2/3），Y = [2/3，1]。

这导致以下三个有效情况：

B1。X1中的a，X2中的b，Y中的c

B2。X1中的a，X1中的b，Y中的c

B3。X2中的a，X2中的b，Y中的c

情况B1和B3：三个数字的总和始终大于1，因此我们取最小值，然后检查其是否小于2。

情况B2：三个数字的总和总是小于2，因此我们取最大和并检查是否大于1。

综上所述，测试是：

• |X| >= 3 和 Xmax(1) + Xmax(2) + Xmax(3) >= 1
• |X| >= 2，|Z| >= 1和Xmin(1)+Xmin(2)+Zmin(1) <= 2
• |X| >= 1，|Y| >= 2和Xmin(1)+Ymin(1)+Ymin(2) <= 2
• |X| >= 1，|Y| >= 1，|Z| >= 1，和Xmin(1)+Ymin(1)+Zmin(1) <= 2
• |X| >= 2，|Y| >= 1和Xmax(1) + Xmax(2) + Ymin(1) < 2
• |X| >= 2，|Y| >= 1和Xmin(1) + Xmin(2) + Ymax(1) > 1）

每个测试都可以在线性时间和恒定空间中进行（您只需要查找Xmax(1), Xmax(2), Xmax(3), Xmin(1), Xmin(2), Ymin(1), Ymin(2), Ymax(1), Zmin(1)，即使没有对数据进行排序，也可以一次找到所有这些）