Знайдзіце ўсе трайняты з нулявой сумай


Узровень складанасці серада
Часта пытаюцца ў амазонка GE Healthcare 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. ўсталяваць Boolean пераменная isFound да ілжывага.
  3. Пятля ад i = 0 да i
    1. Усталёўка елка = i + 1, сек = n-1 і іншая зменная x да бягучага элемента масіва.
    2. Пакуль елка
      1. Праверце, ці ўтвараюць тры элементы разам суму 0.
        1. Калі true, то надрукуйце ўсе тры нумары і ўсталюйце isFound у true.
      2. Праверце, калі сума трох элементаў (бягучых элементаў масіва) меншая за 0.
        1. Калі дакладна, павялічце значэнне піхты на 1.
      3. Праверце інакш, калі сума трох элементаў большая за 0.
          1. Калі дакладна, зменшыце значэнне сек на 1.
  4. Праверце, калі isFound застаецца ілжывым, гэта азначае, што тройні не могуць быць сфармаваны.

Тлумачэнне

Нам дадзены масіў. Тады нам прапануецца вызначыць тройкі, якія можна ўтварыць з зададзенымі лікамі ў масіве, сума якога роўная 0. Мы збіраемся выкарыстоўваць укладзены цыкл. Гэты алгарытм можа працаваць у пастаяннай прасторы. Па-першае, мы збіраемся сартаваць масіў. Такім чынам, мы можам выкарыстаць тэхніку з двума паказальнікамі. Мы аб'явім адну лагічную зменную і спачатку ўсталюем яе значэнне як false. Гэта проста для таго, каб пераканацца, што мы не знойдзем ніводнага з трыплетаў, у якіх элементы складаюць 0, значэнне isFound застаецца ілжывым. Тады мы збіраемся абнаўляць яго да true, калі знойдзем трыплет. Такім чынам, з гэтага можна зрабіць выснову, што трыплет не знойдзены.

Спачатку мы адсартуем масіў ва ўкладзеным цыкле. Затым мы пераходзім масіў да n-1. Мы ўсталюем пачатковае значэнне як i + 1, апошняе значэнне - n-1, а x - бягучае значэнне ў знешнім цыкле. Ва ўнутраным цыкле мы пройдзем значэнні масіва і праверым, ці роўная сума ўсіх трох элементаў (x + arr [fir] + arr [sec]) 0 ці не. Калі ён апынецца роўным 0, гэта азначае, што мы знайшлі першую пару і раздрукуем усе бягучыя значэнні масіва, а для значэння isFound - 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) часу.

Касмічная складанасць

O (1) бо дадатковае месца не патрабуецца.