Бардык уникалдуу триплдер, берилген мааниге чейин


Кыйынчылык деңгээли орто
Көп суралган Accolite Amazon динчилдер
согуштук тизме Hashing издөө

Биз берген согуштук тизме бүтүн сандар жана "сумма" деп аталган берилген сан. Проблеманын чечими берилген суммага кошулган үчөөнү табууну суранат.

мисал

киргизүү:

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

суммасы = 16

Output:

(3, 7, 6), (5, 5, 6)

Explanation:

Берилген суммага барабар үчтүк.

киргизүү:

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

суммасы = 20

Output:

Берилген номер менен түзүлө турган үчөө жок

Algorithm

  1. Берилген массивди иреттөө.
  2. Логикалык өзгөрмө isFound жалганга коюңуз.
  3. I = 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 жалган бойдон кала берсе, анда үч эмдин пайда болушу мүмкүн эмес деген тыянакка келиңиз.

түшүндүрүү

Биз түрү массив биринчи кезекте маанилердин көбөйүшү үчүн, анткени биз колдонобуз экилик издөө жакындап, бир аз. Биз жарыялаганы жатабыз Логикалык өзгөрүлмө жана адегенде анын маанисин жалган деп койсоңуз, үчтүк табылар замат аны жаңыртабыз. Бул элементтер берилген үчөөнүн бирөөсүн таппасак, анда берилген маани ушул бойдон кала берет, биз үч эсе тапканда аны чын деп жаңыртабыз, ошондуктан , биз үч эм тапкан жок деп жыйынтык чыгарсак болот.

Массивди иреттегенден кийин, салынган циклден баштап, n-1 узундугуна чейин массивди аралайбыз. Өзгөрмө маанилердин бирин i + 1, дагы бир маанисин n-1 кылып коюу. Ички циклде биз массивдин бардык баалуулуктарын аралап өтүп, берилген 'сумма' саны массивдин үч элементинин суммасына барабар экендигин текшеребиз (arr [i] + arr [j] + arr [k ]) барабар же тең эмес. Эгер шарт канааттандырылса, анда биз массивдин учурдагы бардык баалуулуктарын басып чыгарабыз жана isFound маанисин true деп койсок, анда жалган маанини кайтарбоо керек.

Эгерде массивдин учурдагы үч маанисинин суммасы берилген санга барабар болбосо, анда учурдагы үч элементтин суммасы берилген суммадан аз болсо, эгер ал суммадан аз болсо, анда анын маанисин көбөйтөбүз j, сол жакты көрсөткөн сол көрсөткүчтү билдирет өтүү жогорулайт жана эгерде бул шарт дагы канааттандырбаса, анда сумманын суммадан чоң экендигин текшеребиз, эгер чын болсо, анда 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]

Бардык уникалдуу триплет үчүн Java программасы, ал берилген мааниге жетет

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 (n2кайда "N" массивдеги элементтердин саны.

Космостун татаалдыгы

O (N) кайда "N" массивдеги элементтердин саны.