三和的范围内的总和(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.所以为了做到这一点,我们只需要测试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.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),即使数据未排序,所有这些都可以在一次通过中找到)

Answer 2

因此，您有一个长度为 n 的 double 数据类型数组。将三个变量 a、b 和 c 初始化为数组的前 3 个值。现在，从 i = 3 迭代到 n 并检查以下内容： 1）检查 sum 是否落在 (1, 2) 中，如果是则返回 true。2）如果不是，则检查 sum 是否大于 2，如果是，则将 MAX(a,b,c) 替换为当前元素 arr[i]。3) 否则 sum 必须小于 1，然后将 MIN(a,b,c) 替换为当前元素 arr[i]。最后，如果 sum 落在 (1,2) 中，则在退出循环后再次检查最后一个三元组返回真，否则返回假。

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;
}