Берілген мәнге дейін жинақталған барлық бірегей үштіктер  


Күрделілік дәрежесі орта
Жиі кіреді Акколит Amazon Фанатика
Array Хэш іздеу

Біз ан массив бүтін сандар және 'қосынды' деп аталатын берілген сан. Проблемалық шешім берілген «қосынды» санына қосылатын үштікті табуды сұрайды.

мысал  

Кіру:

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

қосынды = 16

Шығару:

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

Түсіндіру:

Берілген қосындыға тең үштік.

Кіру:

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

қосынды = 20

Шығару:

Берілген санмен жасалатын үштіктер жоқ

Алгоритм  

  1. Берілген жиымды сұрыптаңыз.
  2. Логикалық айнымалысы isFound-ты жалғанға қойыңыз.
  3. I = 0-ден i-ге дейін
    1. J = i + 1, k = n-1 мәндерін орнатыңыз.
    2. Әзірге j <k
      1. Элементтердің үшеуі берілген қосындыға қосылатындығын тексеріңіз.
        1. Егер шын болса, онда барлық үш санды басып шығарыңыз және «Ақиқат» мәнін орнатыңыз.
      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» - бұл массивтегі элементтер саны.