三联其总和的范围（1,2） [英] Triplet whose sum in range (1,2)

问题描述

由于 N 阵列中的正实数，寻找是否有的存在的三重   这组中，使得，三联体的总和的范围为（1，   2）。做到这一点的线性时间和恒定的空间。

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

任何帮助将是很大的AP preciated。谢谢你。

Any help would be greatly appreciated. Thanks.

推荐答案

关键是要找出一种方法来分类可能的解决方案，并拿出每个线性时间恒定的空间解决方案。

The trick is to figure out a way to categorize the possible solutions and come up with a linear-time constant-space solution for each.

考虑三个范围 X =（0,2 / 3），Y = [2 / 3,1]，Z =（1,2）。最多一个值可能来自以Z （如果两个数值都来自以Z ，那么总和将超过 1 + 1 = 2 ）。同样地，至少有一个值必须来自 X 。假设有3个值 A＆LT; = B＆LT; = C 让 1＆LT; = A + B + C＆LT; = 2 。那么，考虑一下解决方案，可能的类是可行的：

Consider the three ranges X = (0,2/3), Y = [2/3,1], Z = (1,2). At most one value can come from Z (if two values came from Z, then the sum would exceed 1+1=2). Similarly, at least one value must come from X. Suppose there were 3 values a <= b <= c so that 1 <= a+b+c <= 2 . Then, consider what possible classes of solutions are feasible:

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` 

那么怎样才能测试每一种情况？

So how can we test each case?

案例A是非常容易的测试：总和保证低于2，所以我们只需要测试的最大的一笔（在X最大的3个元素）超过1

Case A is incredibly easy to test: the sum is guaranteed to be below 2, so we just need to test the largest sum (largest 3 elements in X) exceeds 1.

案例C是非常容易的测试：由于总和是保证高于1，我们只需要检查总和低于2。因此，为了做到这一点，我们只需要在测试中最小2值X和Z中的最小值

Case C is incredibly easy to test: since the sum is guaranteed to be above 1, we only need to check if the sum is below 2. So in order to do that, we just need to test the smallest 2 values in X and the smallest value in Z

例D和E是类似于C（因为总和必须至少为4/3> 1，选择在每个类的最小可能值）。

Cases D and E are similar to C (since the sum must be at least 4/3 > 1, choose the smallest possible values in each class).

方案B是唯一棘手的情况。 0℃ A + B＆LT; 4/3 和 2/3＆LT; = C＆LT; = 1 。为了处理情况B，我们认为这些间隔：X1 =（0，1/2），X2 = [1/2 2/3），Y = [2/3，1]。

Case B is the only tricky case. 0 < a+b < 4/3 and 2/3 <= c <= 1. To handle case B, we consider these intervals : X1 = (0, 1/2), X2 = [1/2 2/3), Y = [2/3, 1].

这将导致以下三种有效的情况：

This results in following three valid cases :

B1。一个在X1，b在X 2，C Y轴

B1. a in X1, b in X2, c in Y

B2。一个在X1，B的X1，C Y轴

B2. a in X1, b in X1, c in Y

B3。一个在X2，b在X 2，C Y轴

B3. a in X2, b in X2, c in Y

案例B1和放大器; B3：三个数总和总是大于1，所以我们取最低值，并检查它是否小于2或没有。

Case B1 & B3 : Sum of three numbers is always greater than 1 so we take minimum values and check if it is smaller than 2 or not.

案例B2：三个数总和总是小于2，因此，我们采取最高金额，并检查是否大于1或不

Case B2 : Sum of three numbers is always less than 2, so we take maximum sum and check if is greater than 1 or not.

总结一下，测试是：

• | x | ＆GT; = 3 和 Xmax的（1）​​+ Xmax的（2）+ Xmax的（3）＆GT; = 1
• | x | ＆GT; = 2 ， | Z | ＆GT; = 1 和在Xmin（1）+在Xmin（2）+按照Zmin（1） - = = 2
• | x | ＆GT; = 1 ， | Y | ＆GT; = 2 和在Xmin（1）+ YMIN（1）+ YMIN（2）＆LT; = 2
• | x | ＆GT; = 1 ， | Y | ＆GT; = 1 ， | Z | ＆GT; = 1 和在Xmin（1）+ YMIN（1）+按照Zmin（1） - = = 2
• | x | ＆GT; = 2 ， | Y | ＆GT; = 1 和 Xmax的（1）​​+ Xmax的（2）+ YMIN（1） - ; 2
• | x | ＆GT; = 2 ， | Y | ＆GT; = 1 和在Xmin（1）+在Xmin（2）+ YMAX（1）＆GT; 1 ）

• |X| >= 3 and Xmax(1) + Xmax(2) + Xmax(3) >= 1
• |X| >= 2, |Z| >= 1, and Xmin(1)+Xmin(2)+Zmin(1) <= 2
• |X| >= 1, |Y| >= 2, and Xmin(1)+Ymin(1)+Ymin(2) <= 2
• |X| >= 1, |Y| >= 1, |Z| >= 1, and Xmin(1)+Ymin(1)+Zmin(1) <= 2
• |X| >= 2, |Y| >= 1, and Xmax(1) + Xmax(2) + Ymin(1) < 2
• |X| >= 2, |Y| >= 1, and 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），所有这些都可以在即使数据未排序一个道次中找到）

Each test can be performed in linear time and constant space (you only need to find Xmax(1), Xmax(2), Xmax(3), Xmin(1), Xmin(2), Ymin(1), Ymin(2), Ymax(1), Zmin(1), all of which can be found in one pass even if the data is not sorted)

这篇关于三联其总和的范围（1,2）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！