Пронађите све тројке са нултом сумом


Ниво тешкоће Средњи
Често питани у амазонка ГЕ Хеалтхцаре гоогле Пешачење
Ред Хасх Претраживање сортирање

Проблем „Пронађи све тројке са нултом сумом“ наводи да ти се даје низ који садржи и позитиван и негативан број. Изјава о проблему тражи да се сазна тројка са збиром једнаким 0.

Пронађите све тројке са нултом сумом

Пример

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

Објашњење

То су тројке чија је сума 0.

(-2 + -1 + 3 = 0) (-2 + 0 + 2 = 0) (-1+ 0 + 1 = 0)

arr[] = {2,4,-5,-1,3}
(-5 2 3)

Објашњење

То су тројке чији је збир бројева 0 ⇒ -5 + 2 + 3 = 0

Алгоритам

  1. Врста дати низ.
  2. Подесите Боолеан варијабла се налази на лажно.
  3. Петљање од и = 0 до и
    1. Сет јела = и + 1, сек = н-1 а друга променљива x тренутном елементу низа.
    2. Док јелка
      1. Проверите да ли три елемента заједно чине збир 0.
        1. Ако је тачно, испишите сва три броја и поставите јеФоунд на труе.
      2. Проверите да ли је збир три елемента (тренутни елементи низа) мањи од 0.
        1. Ако је тачно, тада повећајте вредност јеле за 1.
      3. Проверите да ли је збир три елемента већи од 0.
          1. Ако је тачно, смањите вредност сек за 1.
  4. Проверите да ли исФоунд остаје нетачан, то значи да не могу да се формирају тројке.

Објашњење

Добили смо низ. Тада се од нас тражи да одредимо тројке које се могу формирати са датим бројевима у низу чији је збир 0. Користићемо угнежђену петљу. Овај алгоритам може радити у сталном простору. Прво ћемо сортирати низ. На овај начин можемо користити технику двосмерца. Прогласићемо једну логичку променљиву и прво ћемо јој поставити вредност фалсе. Ово је само да бисмо осигурали да нећемо наћи ниједан од тројки који имају елементе суме 0, вредност од се налази остаје да буде лажно. Тада ћемо га ажурирати на труе кад год нађемо тројку. Дакле, са овим можемо закључити да није пронађена тројка.

Прво ћемо сортирати низ, у угнежђену петљу. Затим прелазимо низ до н-1. Почетну вредност поставићемо као и + 1, последњу вредност на н-1, а к на тренутну вредност у спољној петљи. У унутрашњој петљи прећи ћемо преко вредности низа и проверити да ли је збир сва три елемента (к + арр [фир] + арр [сец]) једнак 0 или не. Ако се утврди да је 0, то значи да смо пронашли први пар и исписали све тренутне вредности низа, а вредност исФоунд поставили на труе.

То указује да смо пронашли један од парова. Ако збир триплета није једнак 0. Проверавамо да ли је збир три тренутна елемента мањи од 0. Ако је збир мањи од 0. Повећавамо јелу, значи да се повећава наша почетна вредност. Ако услов није задовољен. Проверавамо да ли је збир већи од 0. Ако је тачно, онда се смањује сек.

На овај начин ћемо пронаћи све могуће тројке које се могу збројити на 0.

Ц ++ код за проналажење свих тројки са нултом сумом

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}
(-2 -1 3)
(-2 0 2)
(-1 0 1)

Јава код за проналажење свих тројки са нултом сумом

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}
(-2 -1  3)
(-2 0  2)
(-1 0  1)

Анализа сложености

Сложеност времена

На2) где „Н“  је број елемената у низу. Пошто користимо технику са два показивача која доприноси О (н) времену. Али сама техника се користи О (н) време. Тако се алгоритам покреће за О (н ^ 2) време.

Сложеност простора

О (1) јер није потребан додатни простор.