Пронајдете ги сите тројки со нула збир  


Ниво на тешкотија Медиум
Често прашувано во Амазон ГЕ здравство Google Крстоносните
Низа Хаш Пребарување Сортирање

Проблемот „Пронајди ги сите тројки со нула збир“ вели дека ти е дадена низа што содржи и позитивен и негативен број. Изјавата за проблемот бара да се открие тројката со збир еднаков на 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. Јамка од i = 0 до i
    1. Намести ела = i + 1, сек = n-1 и друга променлива x до тековниот елемент на низата.
    2. Додека ела
      1. Проверете дали три од елементите заедно формираат збир од 0.
        1. Ако е точно, тогаш отпечатете ги сите три број и поставете еFound to true.
      2. Проверете дали збирот на три елементи (тековни елементи на низата) е помал од 0.
        1. Ако е точно, тогаш зголемете ја вредноста на елата за 1.
      3. Проверете на друго место дали збирот на трите елементи е поголем од 0.
          1. Ако е точно, тогаш намалете ја вредноста на сек за 1.
  4. Проверете дали isFound останува лажен, тоа значи дека не може да се формираат тројки.

Објаснување

Ни е дадена низа. Потоа од нас се бара да ги одредиме тројките што можат да се формираат со дадените броеви во низа чиј збир е 0. toе користиме вгнездена јамка. Овој алгоритам може да работи во постојан простор. Прво, ќе ја средиме низата. На овој начин можеме да ја искористиме техниката со два покажувачи. Declaе прогласиме една Булова променлива и ќе ја поставиме нејзината вредност на неправилна на почетокот. Ова е само за да се осигура дали нема да најдеме ниту една од тројките што имаат елементи збир до 0, вредноста на најдено е останува да биде лажен. Тогаш ќе го ажурираме на вистинито секогаш кога ќе најдеме тројка. Значи, со ова, можеме да заклучиме дека не е пронајдена тројка.

Видете исто така
Избриши и заработи

Прво ќе ја сортираме низата, во вгнездената јамка. Потоа ја минуваме низата до n-1. Почетната вредност ќе ја поставиме i + 1, последната вредност n-1, а x на тековната вредност во надворешната јамка. Во внатрешната јамка ќе ги пресечеме вредностите на низата и ќе провериме дали збирот на сите три елементи (x + arr [ела] + arr [сек]) е еднаков на 0 или не. Ако се утврди дека е 0, тоа значи дека го пронајдовме првиот пар и ги отпечативме сите тековни вредности на низата, и поставивмеFound value во true.

Ова укажува дека најдовме еден од паровите. Ако збирот на тројка не е еднаков на 0. Проверуваме дали збирот на три тековни елементи е помал од 0. Ако збирот е помал од 0. Ние ја зголемуваме елата, значи дека нашата почетна вредност е зголемена. Ако состојбата не е задоволена. Проверуваме дали збирот е поголем од 0. Ако е точно, тогаш се намалува сек.

На овој начин, ќе ги најдеме сите можни тројки што можат да бидат збир до 0.

C ++ код за да ги пронајдете сите тројки со нула сума  

#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)

Java код за да ги пронајдете сите тројки со нула збир  

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) каде „Н“  е бројот на елементи во низата. Бидејќи користиме две техники за покажувачи кои придонесуваат за O (n) време. Но, самата техника се користи за O (n) време. Така, алгоритмот работи во O (n ^ 2) време.

Видете исто така
3 Збир

Комплексноста на просторот

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