给定
n数组中的正实数，找出该集合中是否存在三元组，使得三元组的总和在范围内(1, 2)。在线性时间和恒定空间中进行。
- 数组未排序。
- 数字为正
- 数字是实数
任何帮助将不胜感激。谢谢。
诀窍是找出一种方法对可能的解决方案进行分类，并为每个解决方案提出一个线性时间恒定空间解决方案。
考虑这三个范围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)，即使没有对数据进行排序，也可以一次找到所有这些测试）
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句