Триплет, сумма которого находится в диапазоне (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, поэтому нам просто нужно проверить, что наибольшая сумма (3 самых больших элемента в X) превышает 1.

Случай C невероятно легко проверить: поскольку сумма гарантированно больше 1, нам нужно только проверить, меньше ли сумма 2. Поэтому для этого нам просто нужно проверить 2 наименьших значения в X и наименьшее значение в 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 in X1, b in X2, c in Y

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

B3. a in X2, b in X2, c in 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), все из которых можно найти за один проход, даже если данные не отсортированы)

Итак, у вас есть массив двойных типов данных длины n. Инициализируйте три переменные a, b и c как первые 3 значения массива. Теперь выполните итерацию от i = 3 до n и проверьте следующее: 1) Проверьте, попадает ли сумма в (1, 2), если она возвращается, то возвращает true. 2) Если нет, то проверьте, больше ли сумма 2, если да, то замените MAX(a,b,c) на текущий элемент arr[i]. 3) В противном случае сумма должна быть меньше 1, затем замените MIN (a, b, c) на текущий элемент arr [i]. И, наконец, после выхода из цикла проверьте еще раз последнюю тройку, если сумма попадает в (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;
}

Заданный вопрос аналогичен этому 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;
}

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

Эта проблема может быть легко решена в линейном времени выполнения с использованием подхода скользящей суммы окна. В этом случае мы будем использовать окно размером 3. Это также называется «алгоритмом скользящей суммы».

Алгоритм ниже

1> Prepare the window of size 3 with the first 3 elements
2> IF (array.len <= 3): CHECK IF window-sum is in the range (1,2), then RETURN accordingly
3> FOR i = 3 UPTO (array.len-1)
3.1> SORT the window (3log3 = constant time operation)
3.2> IF window-sum is in the range (1,2): RETURN 1 or TRUE
3.3> ELSE IF window-sum < 1: Replace the smallest element in the window (window[0]) with array[i]
3.4> ELSE IF window-sum > 2: Replace the largest element in the window (window[2]) with array[i]
4> Outside the loop, check the FINAL window sum and RETURN accordingly.

Доступ к коду Python здесь. Пометьте репозиторий, пожалуйста!

Код Java для решения, предоставленного @soul Ec.

нам нужно изменить случай B. допустим, наши числа равны a+b+c

there are three ranges 
    x1        x2           y  
 (0,1/2)   (1/2,2/3)    (2/3,1) 

we have 4 possibilities
1.   x1 + x1 +y
2.   x2 + x2 +y
3.   x1 + x2 +y
4    x2 + x1 +y

здесь случай 3 и 4 идентичны, так как их сумма будет одинаковой. поэтому у нас есть только 3 случая.

1.  x1 + x1 + y it is always <2         ( do x1max+x1max+ymax <2 to verify)
so we have to check if x1max(1)+x1max(2)+ymax(1) > 1
2. x2 + x2 + y it is always >1          ( do x2min+x2min+ymin >1 to verify)
so we have to check if x2min(1)+x2min(2)+ymin(1) <=2
3. x1 + x2 + y it is always >1           (do x1min+x2min+ymin >1 to verify)
so we have to check if x1min(1)+x2min(1)+ymin(1)<=2 

   public static int solve(ArrayList<String> A) {

      double d[]= new double[A.size()];
      for(int i=0;i<A.size();i++) {
          d[i]= Double.parseDouble(A.get(i));
      }


       double range1 = 0;
       double range2 = (double) 2/3;
       double range3 = 1;
       double range4 = 2;

       double range02 =(double) 1/2;

       // min and max in range (0,2/3)
       double min1= Double.MAX_VALUE;
       double min2=Double.MAX_VALUE;
       double min3=Double.MAX_VALUE;

       double max1= Double.MIN_VALUE;
       double max2=Double.MIN_VALUE;
       double max3=Double.MIN_VALUE;

       // min and max in range (2/3,1)
       double miny1= Double.MAX_VALUE;
       double miny2=Double.MAX_VALUE;
       double miny3=Double.MAX_VALUE;


       double maxy1= Double.MIN_VALUE;
       double maxy2=Double.MIN_VALUE;
       double maxy3=Double.MIN_VALUE;

       // min and max in range (1,2)
       double minz1= Double.MAX_VALUE;
       double minz2=Double.MAX_VALUE;
       double minz3=Double.MAX_VALUE;

       double maxz1= Double.MIN_VALUE;
       double maxz2=Double.MIN_VALUE;
       double maxz3=Double.MIN_VALUE;

        // min and max in range (0,1/2)
       double minxx1= Double.MAX_VALUE;
       double minxx2=Double.MAX_VALUE;
       double minxx3=Double.MAX_VALUE;

       double maxx1= Double.MIN_VALUE;
       double maxx2=Double.MIN_VALUE;
       double maxx3=Double.MIN_VALUE;

       // min and max in range (1/2,2/3)
       double minyy1= Double.MAX_VALUE;
       double minyy2=Double.MAX_VALUE;
       double minyy3=Double.MAX_VALUE;

       double maxyy1= Double.MIN_VALUE;
       double maxyy2=Double.MIN_VALUE;
       double maxyy3=Double.MIN_VALUE;




    for (int i = 0; i < d.length; i++) {
        if (d[i] >= range1 && d[i] < range02) {
            if (d[i] < minxx3) {
                minxx1=minxx2;
                minxx2=minxx3;
                minxx3 = d[i];


            } else if (d[i] > minxx3 && d[i] < minxx2) {
                minxx1=minxx2;
                minxx2 = d[i];

            } else if (d[i] > minxx3 && d[i] > minxx2 && d[i] < minxx1) {
                minxx1 = d[i];
            }

            if (d[i] > maxx3) {
                maxx1=maxx2;
                maxx2=maxx3;
                maxx3 = d[i];
            } else if (d[i] < maxx3 && d[i] > maxx2) {
                maxx1=maxx2;
                maxx2 = d[i];
            } else if (d[i] < maxx3 && d[i] < maxx2 && d[i] > maxx1) {
                maxx1 = d[i];
            }


        }

        if (d[i] >= range02 && d[i] < range2) {
            if (d[i] < minyy3) {
                minyy1=minyy2;
                minyy2=minyy3;
                minyy3 = d[i];


            } else if (d[i] > minyy3 && d[i] < minyy2) {
                minyy1=minyy2;
                minyy2 = d[i];

            } else if (d[i] > minyy3 && d[i] > minyy2 && d[i] < minyy1) {
                minyy1 = d[i];
            }

            if (d[i] > maxyy3) {
                maxyy1=maxyy2;
                maxyy2=maxyy3;
                maxyy3 = d[i];
            } else if (d[i] < maxyy3 && d[i] > maxyy2) {
                maxyy1=maxyy2;
                maxyy2 = d[i];
            } else if (d[i] < maxyy3 && d[i] < maxyy2 && d[i] > maxyy1) {
                maxyy1 = d[i];
            }


        }


        if (d[i] >= range1 && d[i] < range2) {
            if (d[i] < min3) {
                min1=min2;
                min2=min3;
                min3 = d[i];


            } else if (d[i] > min3 && d[i] < min2) {
                min1=min2;
                min2 = d[i];

            } else if (d[i] > min3 && d[i] > min2 && d[i] < min1) {
                min1 = d[i];
            }

            if (d[i] > max3) {
                max1=max2;
                max2=max3;
                max3 = d[i];
            } else if (d[i] < max3 && d[i] > max2) {
                max1=max2;
                max2 = d[i];
            } else if (d[i] < max3 && d[i] < max2 && d[i] > max1) {
                max1 = d[i];
            }


        }

        if (d[i] >= range2 && d[i] < range3) {
            if (d[i] < miny3) {
                miny1=miny2;
                miny2=miny3;
                miny3 = d[i];


            } else if (d[i] > miny3 && d[i] < miny2) {
                miny1=miny2;
                miny2 = d[i];

            } else if (d[i] > miny3 && d[i] > miny2 && d[i] < miny1) {
                miny1 = d[i];
            }

            if (d[i] > maxy3) {
                maxy1=maxy2;
                maxy2=maxy3;
                maxy3 = d[i];
            } else if (d[i] < maxy3 && d[i] > maxy2) {
                maxy1=maxy2;
                maxy2 = d[i];
            } else if (d[i] < maxy3 && d[i] < maxy2 && d[i] > maxy1) {
                maxy1 = d[i];
            }


        }


        if (d[i] >= range3 && d[i] <= range4) {
            if (d[i] < minz3) {
                minz1=minz2;
                minz2=minz3;
                minz3 = d[i];


            } else if (d[i] > minz3 && d[i] < minz2) {
                minz1=minz2;
                minz2 = d[i];

            } else if (d[i] > minz3 && d[i] > minz2 && d[i] < minz1) {
                minz1 = d[i];
            }

            if (d[i] > maxz3) {
                maxz1=maxz2;
                maxz2=maxz3;
                maxz3 = d[i];
            } else if (d[i] < maxz3 && d[i] > maxz2) {
                maxz1=maxz2;
                maxz2 = d[i];
            } else if (d[i] < maxz3 && d[i] < maxz2 && d[i] > maxz1) {
                maxz1 = d[i];
            }


        }




       }

    if(max1+max2+max3>=1 && max1!=Double.MIN_VALUE && max2!=Double.MIN_VALUE && max3!=Double.MIN_VALUE) 
        return 1;

    if(min3+min2+minz3<=2 && min3!=Double.MAX_VALUE && min2!=Double.MAX_VALUE && minz3!=Double.MAX_VALUE ) 
        return 1;

    if(min3+miny3+miny2<=2 && min3!=Double.MAX_VALUE && miny3!=Double.MAX_VALUE && miny2!=Double.MAX_VALUE)
       return 1;
    if(min3+miny3+minz3<=2 && min3!=Double.MAX_VALUE && miny3!=Double.MAX_VALUE && minz3!=Double.MAX_VALUE)
        return 1;

    if(maxx3+maxx2+maxy3>1 && maxx3!=Double.MIN_VALUE && maxx2!=Double.MIN_VALUE && maxy3!=Double.MIN_VALUE) {
        return 1;

    }

    if(minyy3+minyy2+miny3<=2 && minyy3!=Double.MAX_VALUE && minyy2!=Double.MAX_VALUE && miny3!=Double.MAX_VALUE) {
        return 1;
    }
    if(minxx3+minyy3+miny3<=2 && minxx3!=Double.MAX_VALUE && minyy3!=Double.MAX_VALUE && miny3!=Double.MAX_VALUE) {
        return 1;
    }




    return 0;






    }

решение находится на С++ (интервьюббит решение)

int Solution::solve(vector<string> &arr) {
int n=arr.size(),i;
vector<float>v;
for(i=0;i<n;i++)
{
    v.push_back(stof(arr[i]));
}
float a=v[0],b=v[1],c=v[2];

float mx=0;
for(i=3;i<n;i++)
{
    if(a+b+c<2 && a+b+c>1)
        return 1;
    else if(a+b+c>2)
    {
        if(a>b && a>c)
            a=v[i];
        else if(b>a && b>c)
            b=v[i];
        else
            c=v[i];
    }
    else
    {
        if(a<b && a<c)
            a=v[i];
        else if(b<a && b<c)
            b=v[i];
        else
            c=v[i];

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

Мы можем легко сделать это за O(n), нам просто нужно найти три минимальных положительных действительных числа, которые мы можем найти за одну итерацию, и в конце концов, если их сумма лежит между (1,2), то вернуть 1 иначе вернуть 0 .

Проблема в целом в изложенном виде неразрешима. Это связано с тем, что для любых двух действительных чисел a и b нельзя решить, выполняется ли a > b (см. также этот ответ обо мне). Но вам нужно сделать хотя бы одно сравнение действительного числа с целым числом, чтобы решить эту проблему. Сравнение с целым числом не облегчает задачу, поскольку у вас может быть действительное число, равное 2,00...001, где между цифрами 2 и 1 есть произвольное количество нулей, которое вы заранее не знаете. Хранение таких действительных чисел (вероятно, не всех, но многих) в оперативной памяти компьютера не представляет большой проблемы для таких конкретных, так как они могут быть представлены алгоритмом аппроксимации.

для получения дополнительной информации я предлагаю прочитать Теорию сложности реальных Функции