ټول ځانګړي دریځونه چې ورکړل شوي ارزښت سره سمون لري  


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

موږ ورکړل سور د عدد شمیره او ورکړل شوې شمیری ته 'جمع' وایی. د ستونزې بیان د دریځ موندلو غوښتنه کوي چې ورکړل شوي شمیره 'جمع' اضافه کوي.

بېلګه  

تفتیش:

تیر [] = {3,5,7,5,6,1،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

جمع = 16

محصول:

(3 ، 7 ، 6) ، (5 ، 5 ، 6)

وضاحت:

دریمه برخه چې ورکړل شوې پیسو سره مساوي ده.

تفتیش:

تیر [] = {3,4,1,5,4،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

جمع = 20

محصول:

هیڅ دریځونه شتون نلري چې د ورکړل شوي شمیر سره رامینځته کیدی شي

الګوریتم  

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

تشریح  

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

هم وګوره
لومړۍ خرابه نسخه

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

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

دا به تر هغه وخته پورې وي چې د صف ټول ارزښتونه تعقیب شي. او موږ د isFound ارزښت بیرته راوړو ، کوم چې ریښتیا کیدی شي بیرته راستنیدلی شي که چیرې موږ کوم درې واړه او غلط وموندل که هیڅ ونه موندل شو.

تطبیق  

C ++ برنامې د ټولو ځانګړي درې ګونو لپاره چې ورکړل شوي ارزښت سره سمون لري

#include<iostream>
#include<algorithm>

using namespace std;

int getTripletOfSum(int arr[], int n, int sum)
{
    int i, j, k;
    bool isFound=false;
    sort(arr, arr + n);
    for(i = 0; i < n - 2; i++)
    {
        j = i + 1;
        k = n - 1;

        while(j < k)
        {
            if(arr[i] + arr[j] + arr[k] == sum)
            {
                cout<<"["<<arr[i]<<" "<<arr[j]<<" "<<arr[k]<<"]"<<endl;
                j++;
                k--;
                isFound=true;
            }
            else if(arr[i] + arr[j] + arr[k] > sum)
                k--;
            else
                j++;
        }
    }
    return isFound;
}
int main()
{
    int nums[] = {3,5,7,5,6,1};
    int n = sizeof(nums) / sizeof(nums[0]);
    int sum = 16;
    if(!getTripletOfSum(nums, n, sum))
        cout << "There are no triplets that can be formed with the given number";

    return 0;
}
[3 6 7]
[5 5 6]

د ټولو ځانګړي درې ګونو لپاره جاوا برنامې چې ورکړل شوي ارزښت سره سمون لري

import java.util.Arrays;

public class TripletsWithSum
{
    public static boolean getTripletOfSum(int arr[], int sum)
    {
        Arrays.sort(arr);

        boolean isFound=false;

        for (int i = 0; i < arr.length - 2; i++)
        {
            int j = i + 1;
            int k = arr.length - 1;
            while (j < k)
            {
                if (arr[i] + arr[j] + arr[k] == sum)
                {
                    System.out.println("["+arr[i] + " " + arr[j] +" " +arr[k]+"]");
                    j++;
                    k--;
                    isFound=true;
                }
                else if (arr[i] + arr[j] + arr[k] < sum)
                    j++;

                else
                    k--;
            }
        }
        return isFound;
    }
    public static void main(String[] args)
    {
        int arr[] = {3,5,7,5,6,1};
        int sum = 16;
        if (!getTripletOfSum(arr, sum))
        {
            System.out.println("There are no triplets that can be formed with the given number");
        }
    }
}
[3 6 7]
[5 5 6]

د ټولو ځانګړي درې ګونو لپاره د پیچلو تحلیلونو چې ورکړل شوي ارزښت سره سمون لري  

د وخت پیچلتیا

O (n)2هلته "n" په صف کې د عناصرو شمیر دی.

هم وګوره
بيرته تنظیم کړئ لکه حتی د شاخص عنصرونه کوچني دي او د غیر عادي شاخص عناصر ډیر دي

د ځای پیچلتیا

اې (N) هلته "n" په صف کې د عناصرو شمیر دی.