ټول صفر د صفر جمع سره ومومئ


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon په روبل روغتيا د ګوګل هیک
پیشه هاش لټون کول ترتیب کول

ستونزه "ټول صفر د صفر سره ومومئ" په ګوته کوي چې تاسو ته یو داسې سیر ورکړل شوی چې مثبت او منفي دواړه پکې شتون لري. د ستونزې بیان غوښتنه کوي ترڅو د 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 = XNUMX دی

الګوریتم

  1. ننداره ورکړل شوی صف.
  2. جوړ کړئ بولین متغیر موندل غلط ته.
  3. له i = 0 څخه i ته لوپ کول
    1. ټاکل شوی فرم = i + 1 ، سیک = n-1 او بل متغیر x اوسني صف عنصر ته.
    2. پداسې حال کې چې فرم
      1. وګوره که چیرې درې عناصر یوځای د 0 جمع رامینځته کړي.
        1. که ریښتیا وي ، نو بیا ټول درې لمبر چاپ کړئ او سم یې له ریښتیني څخه تنظیم کړئ.
      2. وګوره که د دریو عناصرو مجموعه (اوسني سرکي عنصر) له 0 څخه لږ وي.
        1. که ریښتیا وي ، نو د 1 لخوا د فرم ارزښت لوړ کړئ.
      3. نور وګورئ که چیرې د دریو عناصرو مجموعه له 0 څخه لویه وي.
          1. که ریښتیا وي ، نو د 1 لخوا د سیک ارزښت کم کړئ.
  4. وګوره که isFound ناسمه پاتې شي ، پدې معنی چې هیڅ درې (ټپل) رامینځته کیدلی نشي.

تشریح

موږ ته یو صف راکړل شو. بیا موږ څخه غوښتنه کیږي چې درې ګونې وټاکي کوم چې په ورکړل شوي شمیرو سره په صف کې رامینځته کیدی شي چې مجموعه یې 0 ده. موږ به ځړول شوي لاپ وکاروو. دا الګوریتم کولی شي په ثابت ځای کې کار وکړي. لومړی ، موږ د صف ترتیب کوو. پدې توګه موږ کولی شو د دوه نښې ټیکنالوژي وکاروو. موږ به د بولان یو متغییر اعلان کړو او د هغې ارزښت به په لومړي سر کې غلط ته وټاکو. دا یوازې د ډاډ ترلاسه کولو لپاره دی که چیرې موږ به هیڅ یو درې نه ومومو چې عنصرونه یې 0 وي ، ارزښت یې موندل اوس هم غلط دی. بیا موږ دا ریښتیا ته تازه کوو کله چې موږ یو مثلث وموم. نو له دې سره ، موږ کولی شو دې پایلې ته ورسېږو چې هیڅ مثلث نه موندل کیږي.

موږ به سرسري لومړی په ځیر شوي تopیو کې تنظیم کړو. بیا موږ صف ته د N-1 پورې غزوو. موږ به د پیل ارزښت د i + 1 په توګه ، وروستی ارزښت n-1 ته او x به په اوسني ارزښت کې په بهرني لوپ کې وټاکو. په داخلي لوپ کې به موږ د صفونو ارزښتونه تیر کړو ، او وګورو چې ایا د دریو عناصرو (x + آرر [فیر] + آرر [سیک]) مجموعه 0 سره مساوي ده یا نه. که چیرې دا 0 وموندل شي ، نو پدې معنی چې موږ لومړۍ جوړه موندلې او د سرنی ټول اوسني ارزښتونه چاپ کوو ، او isFound ارزښت ریښتیني دی.

دا په ګوته کوي چې موږ یوه جوړه وموندله. که چیرې د درې ګوني مجموعه 0 سره مسله نه وي. موږ ګورو چې د دریو اوسني عناصرو مجموعه له 0 څخه کم ده. که چیرې دا رقم له 0 څخه کم وي. موږ د فرم وده کوو ، پدې معنی چې زموږ د پیل ارزښت لوړ شوی. که حالت مطمئن نه وي. موږ ګورو چې دا مجموعه له 0 څخه لوړه ده. که ریښتیا وي ، نو بیا کمیږي.

پدې لار کې ، موږ ټول احتمالي دریځونه موندلو لپاره چې 0 سره جوخت کیدی شي.

C ++ کوډ د صفر مجموعې سره ټولې درې پا Findې ومومئ

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

د پیچلتیا تحلیل

د وخت پیچلتیا

O (n)2) هلته "n"  په صف کې د عناصرو شمیر دی. له هغه وخته چې موږ دوه نښې ایښودونکي تخنیک کاروو چې د O (n) وخت لپاره برخه اخلو. مګر تخنیک پخپله د O (n) وخت لپاره کارول کیږي. پدې توګه د الګوریتم رامینځته کول په O (n ^ 2) وخت کې.

د ځای پیچلتیا

O (1) ځکه چې اضافي ځای ته اړتیا نشته.