Всички уникални тризнаци, които обобщават дадена стойност


Ниво на трудност M
Често задавани в Аколит Амазонка Фанатиците
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 на false.
  3. Докато i = 0 до i
    1. Задайте j = i + 1, k = n-1.
    2. Докато j <k
      1. Проверете дали три от елементите заедно се добавят към дадената сума.
        1. Ако е вярно, отпечатайте и трите числа и задайте isFound на true.
      2. Проверете иначе дали сумата от трите елемента е по-голяма от сумата.
        1. Ако е вярно, тогава намалете стойността на k с 1.
      3. Проверете дали сумата от три елемента (текущи елементи на масива) е по-малка от сумата.
        1. Ако е вярно, тогава увеличете стойността на j с 1.
  4. Проверете дали isFound остава фалшив, заключава се, че не могат да се образуват тризнаци.

Обяснение

Ние вид масивът първо, за да станат стойностите в нарастващ ред, защото ще използваме a двоично търсене подход, малко. Ще обявим a Булева променлива и първо зададем стойността му на false, ще го актуализираме веднага щом намерим триплета. Това е да се уверим, че ако не намерим нито един от тризнаците, които имат елементи, сумирани към дадено число, стойността isFound остава такава, каквато е, само че ще я актуализираме на true, когато намерим триплет, така че , можем да заключим, че не е намерен триплет.

След сортирането на масива, започвайки от вложения цикъл, ще прекосим масива до дължината n-1. Задаване на една от стойностите на променливата като i + 1, друга стойност на n-1. Във вътрешния цикъл ще преминем през всички стойности на масив и ще проверим дали даденото число 'sum' е равно на сумата от трите текущи елемента на масива (arr [i] + arr [j] + arr [k ]) е равно или не. Ако условието удовлетворява, ще отпечатаме всички текущи стойности на масив и ще зададем стойност isFound на true, това гарантира, че не трябва да връщаме фалшива стойност.

Ако сумата от три текущи стойности на масив не е равна на даденото число, ще проверим дали ако сумата от трите текущи елемента е по-малка от дадената сума, ако е по-малка от сумата, ще увеличим стойността на j, означава нашия ляв показалец, който показва отляво обръщане е увеличение и ако това условие също не отговаря, ще проверим дали сумата е по-голяма от сумата, ако е вярно, тогава ще намалим стойността на k.

Той ще продължи, докато всички стойности на масива не бъдат обходени. И ние ще върнем стойността isFound, която може да бъде върната като истина, ако намерим някой от тризнаците и false, ако не сме намерили такава.

изпълнение

Програма 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]

Анализ на сложността за всички уникални тризнаци, които сумират до дадена стойност

Сложност във времето

На2където "н" е броят на елементите в масива.

Сложност на пространството

О (п) където "н" е броят на елементите в масива.