همه سه قلوها را با جمع صفر پیدا کنید  


سطح دشواری متوسط
اغلب در آمازون GE بهداشت و درمان گوگل پیاده روی
صف مخلوط جستجو مرتب سازی

مسئله "یافتن همه سه گانه ها با مجموع صفر" بیان می کند که به شما آرایه ای حاوی هر دو عدد مثبت و منفی داده می شود. عبارت مسئله می خواهد سه گانه را جمع کند که برابر با 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. تنظیم fir = i + 1، sec = n-1 و یک متغیر دیگر x به عنصر آرایه فعلی.
    2. در حالی که صنوبر است
      1. بررسی کنید که آیا سه عنصر با هم جمع ۰ هستند.
        1. اگر درست است ، سپس هر سه عدد را چاپ کنید و تنظیم کنید isFound to true است.
      2. بررسی کنید که آیا مجموع سه عنصر (عناصر آرایه فعلی) کمتر از 0 است.
        1. اگر درست است ، پس مقدار صنوبر را 1 افزایش دهید.
      3. اگر مجموع سه عنصر بیشتر از 0 است ، دیگری را بررسی کنید.
          1. اگر درست است ، مقدار ثانیه را 1 کاهش دهید.
  4. بررسی کنید isfound نادرست است ، به این معنی است که هیچ سه قلوتی تشکیل نمی شود.

توضیح

به ما آرایه ای داده می شود. سپس از ما خواسته می شود سه تایی را که می توان با اعداد داده شده در آرایه ای که مجموع آنها 0 است تشکیل داد ، تعیین کنیم. ما می خواهیم از یک حلقه تو در تو استفاده کنیم. این الگوریتم می تواند در فضای ثابت کار کند. ابتدا می خواهیم آرایه را مرتب کنیم. به این ترتیب می توانیم از تکنیک دو نشانگر استفاده کنیم. ما یک متغیر Boolean را اعلان می کنیم و مقدار آن را در ابتدا false قرار می دهیم. این فقط برای اطمینان از این است که آیا ما هیچ یک از سه گانه هایی را پیدا نمی کنیم که دارای عناصر جمع به 0 باشند ، مقدار پیدا شده است نادرست باقی مانده است هر وقت یک سه قلو پیدا کنیم ، آنرا به صورت واقعی به روز می کنیم. بنابراین با این کار می توان نتیجه گرفت که هیچ سه قلوتی یافت نمی شود.

همچنین مشاهده کنید
حذف و کسب

ما ابتدا آرایه را در حلقه تو در تو مرتب می کنیم. سپس آرایه را تا n-1 پیمایش می کنیم. ما مقدار شروع را به عنوان i + 1 ، آخرین مقدار را به n-1 و x را به مقدار فعلی در حلقه بیرونی تنظیم خواهیم کرد. در حلقه داخلی مقادیر یک آرایه را رد می کنیم و بررسی می کنیم که آیا جمع سه عنصر (x + arr [fir] + arr [sec]) برابر با 0 باشد یا خیر. اگر مشخص شود که 0 باشد ، این بدان معناست که جفت اول را پیدا کرده و تمام مقادیر فعلی آرایه را چاپ کرده و مقدار isFound را به true تنظیم کرده ایم.

این نشان می دهد که ما یکی از جفت ها را پیدا کرده ایم. اگر مجموع سه گانه برابر با 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)

کد جاوا برای یافتن تمام سه قلوها با جمع صفر  

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) جایی که "n"  تعداد عناصر آرایه است. از آنجا که ما از دو تکنیک اشاره گر استفاده می کنیم که برای زمان O (n) کمک می کند. اما این تکنیک خود برای زمان O (n) استفاده می شود. بنابراین ساخت الگوریتم در زمان O (n ^ 2) انجام می شود.

همچنین مشاهده کنید
3 جمع

پیچیدگی فضا

O (1) زیرا فضای اضافی مورد نیاز نیست.