arrays - 总和在 (1,2) 范围内的三元组

Question

Given n positive real numbers in an array, find whether there exists a triplet among this set such that, the sum of the triplet is in the range (1,
2). Do it in linear time and constant space.

• the array is not ordered.
• numbers are positive
• numbers are real numbers

如有任何帮助，我们将不胜感激。谢谢。

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。因此，为了做到这一点，我们只需要测试最小的 2 个值X和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。 a在X1中，b在X2中，c在Y中

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

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

案例 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)，即使数据没有排序也可以一次找到)