任何帮助将不胜感激。谢谢。
最佳答案
诀窍是找出一种方法对可能的解决方案进行分类，并为每个解决方案提出一个线性时间恒定空间解决方案。
考虑三个范围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)，即使没有对数据进行排序，也可以一次通过所有这些测试)