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


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

ما داده ایم صف از اعداد صحیح و یک عدد داده شده به نام 'sum' است. بیانیه مسئله می خواهد سه گانه ای را جمع کند که به عدد داده شده "مجموع" اضافه می شود.

مثال  

ورودی:

arr [] = {3,5,7,5,6,1،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

جمع = 16

خروجی:

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

شرح:

سه گانه که برابر با جمع داده شده است.

ورودی:

arr [] = {3,4,1,5,4،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

جمع = 20

خروجی:

هیچ سه گانه ای وجود ندارد که بتوان با عدد داده شده تشکیل داد

الگوریتم  

  1. آرایه داده شده را مرتب کنید.
  2. متغیر Boolean isFound را روی false تنظیم کنید.
  3. در حالی که من = 0 تا i هستم
    1. j = i + 1 ، k = n-1 تنظیم کنید.
    2. در حالی که j <k
      1. بررسی کنید که آیا سه عنصر با هم به جمع داده شده اضافه شده است.
        1. اگر درست است ، سپس هر سه عدد را چاپ کنید و تنظیم کنید isFound to true است.
      2. اگر جمع سه عنصر از مجموع بیشتر است ، دیگری را بررسی کنید.
        1. اگر درست است ، مقدار k را 1 کاهش دهید.
      3. بررسی کنید که آیا مجموع سه عنصر (عناصر آرایه فعلی) کمتر از جمع است.
        1. اگر درست است ، مقدار j را 1 افزایش دهید.
  4. بررسی کنید isfound نادرست است یا خیر ، نتیجه می گیرد که هیچ سه قلو نمی تواند تشکیل شود.

توضیح  

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

همچنین مشاهده کنید
اولین نسخه بد

پس از مرتب سازی آرایه ، شروع به حلقه تو در تو ، آرایه را تا طول n-1 پیمایش می کنیم. تنظیم یکی از مقادیر متغیر به عنوان i + 1 ، مقدار دیگر به n-1. در حلقه داخلی ، تمام مقادیر یک آرایه را رد می کنیم و بررسی می کنیم که آیا عدد داده شده 'sum' برابر با جمع سه عنصر آرایه فعلی است (arr [i] + arr [j] + arr [k ]) برابر است یا نه. اگر شرط برآورده شود ، ما می خواهیم تمام مقادیر فعلی یک آرایه را چاپ کنیم و مقدار isFound را به true تنظیم کنیم ، این اطمینان می دهد که ما نباید مقدار نادرستی را بازگردانیم.

اگر مجموع سه مقدار فعلی یک آرایه با عدد داده شده برابر نباشد ، بررسی می کنیم که اگر مجموع سه عنصر فعلی از مجموع داده شده کمتر باشد ، اگر از مجموع کمتر باشد ، مقدار را افزایش می دهیم از j ، به معنی اشاره گر سمت چپ ما است که از سمت چپ نشان می دهد پیمایش افزایش است و اگر این شرط نیز برآورده نکند ما بررسی خواهیم کرد که آیا مجموع بیشتر از مجموع است ، اگر درست باشد ، مقدار k را کاهش می دهیم.

این کار ادامه خواهد یافت تا تمام مقادیر آرایه مورد استفاده قرار گیرد. و ما قصد داریم مقدار isFound را برگردانیم ، که اگر هر یک از سه گانه ها را پیدا کنیم و اگر نتوانستیم نادرست باشد ، می تواند به صورت true برگردانده شود.

پیاده سازی  

برنامه 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]

تحلیل پیچیدگی برای همه سه قلوهای منحصر به فرد که در یک مقدار معین جمع می شوند  

پیچیدگی زمان

بر2جایی که "n" تعداد عناصر آرایه است.

همچنین مشاهده کنید
ترتیب مجدد آرایه به گونه ای است که عناصر شاخص حتی کوچکتر و عناصر شاخص فرد بیشتر هستند

پیچیدگی فضا

O (N) جایی که "n" تعداد عناصر آرایه است.