在范围内和(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。

案例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

Case 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)，所有这些都可以在一次测试中找到，即使数据没有排序)。

Answer 2

因此，您有一个长度为n的双数据类型的数组。将三个变量a、b和c作为array.Now的前3值进行迭代，从i=3迭代到n并检查如下:1)检查sum是否在(1，2)中，如果它返回true。2)如果没有，则检查和是否大于2，如果大于2，则将MAX(a，b，c)替换为当前元素arri。3)否则和必须小于1，然后将最小(a，b，c)替换为当前元素arri.And，在退出循环后，再次检查最后一个三重奏，如果和在(1,2)中，则返回true，否则返回false。

enter code here
double a=arr[0], b=arr[1], c=arr[2];
for(int i=3 ; i<n ; i++){
    // check if sum fall in (1, 2)
    if(a+b+c > 1 && a+b+c < 2){
        return 1;
    }
    // if not, then check is sum greater than 2
    // if so, then replece MAX(a,b,c) to new number
    else if(a+b+c > 2){
        if(a>b && a>c){
            a = arr[i];
        }
        else if(b>a && b>c){
            b = arr[i];
        }
        else if(c>a && c>b){
            c = arr[i];
        }
    }
    // else then sum must be less than 1
    // then replace MIN(a,b,c) to new number
    else{
        if(a<b && a<c){
            a = arr[i];
        }
        else if(b<a && b<c){
            b = arr[i];
        }
        else if(c<a && c<b){
            c = arr[i];
        }
    }
}
// check for last a, b, c  triplet
if(a+b+c > 1 && a+b+c < 2){
    return 1;
}
else{
    return 0;
}

Answer 3

提出的问题类似于这 InterviewBit问题。我对下面提到的解决方案做了一些修改，以完全符合您的要求。

有三个条件：

​

• 首先，如果和在1和2之间。
• 第二，如果和大于2，则三个元素中较大的元素将被替换为下一个元素，并重复该过程。
• 第三，如果和小于1，则三个元素中较小的元素将被替换为下一个元素，并且重复相同的过程。

int Solution::solve(vector<float> &A) {
    if(A.size()<3) return 0;

    float a = A[0];
    float b = A[1];
    float c = A[2];

    for(int i=3;i<A.size();++i){
        if(a+b+c>1 && a+b+c<2)
            return 1;

        float temp = A[i];

        if(a+b+c>=2){
            if(a>b && a>c)
                a = temp;
            else if(b>c && b>a)
                b = temp;
            else
                c = temp;
        }
        else{
            if(a<b && a<c)
                a = temp;
            else if(b<c && b<a)
                b = temp;
            else
                c = temp;
        }
    }

    if(a+b+c>1 && a+b+c<2) return 1;

    return 0;
}

​

同样的问题也可以用两个指针技术来解决。首先，我们必须对数组进行排序。但是，它的复杂性将超过O(logn)。

​

int Solution::solve(vector<float> &A) {
    int n = A.size();

    if(n<3) return 0;
    sort(A.begin(), A.end());

    int l = 0, r = n-1;

    while(l<r-1){
        float s = A[l]+A[l+1]+A[r];
        if(s>=2)
            r = r-1;
        else if(s<1)
            l = l+1;
        else return 1;
    }
    return 0;
}