Все уникальные тройки, которые в сумме дают заданное значение


Сложный уровень средний
Часто спрашивают в Акколит Амазонка Фанатики
массив хеширования Поиск

Мы дали массив целых чисел и заданного числа, называемого «суммой». В постановке задачи предлагается найти тройку, которая в сумме дает заданное число «сумма».

Пример

Входной сигнал:

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. Пока я = от 0 до я
    1. Установите j = i + 1, k = n-1.
    2. Пока j <k
      1. Проверьте, составляют ли три элемента вместе заданную сумму.
        1. Если true, то выведите все три числа и установите isFound в true.
      2. Проверьте еще, если сумма трех элементов больше суммы.
        1. Если это правда, уменьшите значение k на 1.
      3. Проверить, меньше ли сумма трех элементов (текущих элементов массива) суммы.
        1. Если это правда, то увеличьте значение j на 1.
  4. Проверить, остается ли isFound ложным, делает вывод, что триплеты не могут быть сформированы.

объяснение

Мы будем sort массив первым, чтобы значения стали в порядке возрастания, потому что мы собираемся использовать бинарный поиск подход, немного. Мы собираемся объявить Логическая переменная и сначала установите для него значение false, мы собираемся обновить его, как только найдем триплет. Это сделано для того, чтобы убедиться, что, если мы не найдем ни одного из триплетов, сумма элементов которых равна заданному числу, значение isFound останется таким, как есть, только мы собираемся обновить его до true, когда мы нашли триплет, поэтому с этим , можно сделать вывод, что триплет не обнаружен.

После сортировки массива, начиная с вложенного цикла, мы пройдем по массиву до длины n-1. Установка одного из значений переменной как i + 1, другого значения как n-1. Во внутреннем цикле мы пройдемся по всем значениям массива и проверим, равно ли заданное число 'sum' сумме трех текущих элементов массива (arr [i] + arr [j] + arr [k ]) равно или нет. Если условие удовлетворяется, мы собираемся распечатать все текущие значения массива и установить для isFound значение true, это гарантирует, что мы не должны возвращать ложное значение.

Если сумма трех текущих значений массива не равна заданному числу, мы проверим, что если сумма трех текущих элементов меньше заданной суммы, если она меньше суммы, мы увеличим значение of j, означает наш левый указатель, который указывает слева пересечение увеличивается, и если это условие также не выполняется, мы проверим, больше ли сумма, чем сумма. Если это правда, то мы уменьшим значение k.

Это будет продолжаться до тех пор, пока не будут пройдены все значения массива. И мы собираемся вернуть значение isFound, которое может быть возвращено как true, если мы нашли какой-либо из триплетов, и 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в котором «Н» это количество элементов в массиве.

Космическая сложность

О (п) в котором «Н» это количество элементов в массиве.