Գտեք զրոյական գումարով բոլոր եռյակները


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon 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 փոփոխական մեծություն Գտնված է կեղծ:
  3. I = 0-ից i- ի հանգույց
    1. հավաքածու եղեւնի = i + 1, վրկ = n-1 և մեկ այլ փոփոխական x ընթացիկ զանգվածի տարրին:
    2. Մինչ եղեւնին է
      1. Ստուգեք ՝ արդյոք տարրերից երեքը միասին կազմում են 0-ի գումար:
        1. Եթե ​​ճիշտ է, ապա տպիր բոլոր երեք համարները և սահմանիր isFound to true:
      2. Ստուգեք, արդյոք երեք տարրերի (ընթացիկ զանգվածի տարրեր) գումարը 0-ից պակաս է:
        1. Եթե ​​ճիշտ է, ապա եղեւնու արժեքն ավելացրու 1-ով:
      3. Այլ կերպ ստուգեք, արդյոք երեք տարրերի գումարը մեծ է 0-ից:
          1. Եթե ​​ճիշտ է, ապա վրկ-ի արժեքը 1-ով իջեցրու:
  4. Ստուգեք isFound- ը կեղծ է մնում, դա նշանակում է, որ ոչ մի եռյակ չի կարող ստեղծվել:

բացատրություն

Մեզ տրվում է զանգված: Դրանից հետո մեզ խնդրում են որոշել այն եռյակները, որոնք կարող են կազմվել տրված թվերով զանգվածում, որի գումարը 0. է: Մենք մտադիր ենք օգտագործել տեղադրված օղակ: Այս ալգորիթմը կարող է աշխատել անընդհատ տարածության մեջ: Նախ, մենք տեսակավորելու ենք զանգվածը: Այս կերպ մենք կարող ենք օգտագործել երկանից տեխնիկան: Մենք կհայտարարենք մեկ բուլյան փոփոխական և սկզբում դրա արժեքը կսահմանենք կեղծ: Սա պարզապես ապահովելու համար, եթե մենք չգտնենք որևէ եռյակ, որը 0-ի տարրեր ունենա XNUMX-ի, արժեքը Գտնված է մնում է կեղծ: Այդ դեպքում մենք այն թարմացնելու ենք ճշմարիտ, երբ գտնենք եռյակ: Այսպիսով, սրանով մենք կարող ենք եզրակացնել, որ ոչ մի եռյակ չի հայտնաբերվել:

Մենք նախ տեսակավորելու ենք զանգվածը ՝ տեղադրված օղակում: Դրանից հետո մենք անցնում ենք զանգվածը մինչև n-1: Մենք սկզբնական արժեքը կդնենք որպես i + 1, վերջին արժեքը `n-1, իսկ x- ը` արտաքին օղակի ընթացիկ արժեքը: Ներքին օղակում մենք կկողմնորոշվենք զանգվածի արժեքները և ստուգենք, արդյոք բոլոր երեք տարրերի (x + arr [եղևնու + arr [վրկ]) գումարը հավասար է 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)

Բարդության վերլուծություն

Timeամանակի բարդություն

Վրա2) որտեղ «Ն»  զանգվածում տարրերի քանակն է: Քանի որ մենք օգտագործում ենք ցուցիչի երկու տեխնիկա, որոնք նպաստում են O (n) ժամանակի համար: Բայց տեխնիկան ինքնին օգտագործվում է O (n) ժամանակի համար: Այսպիսով ստիպելով ալգորիթմը գործարկել O (n ^ 2) ժամանակում:

Տիեզերական բարդություն

Ո (1) քանի որ լրացուցիչ տարածք չի պահանջվում: