Знайдіть усі триплети з нульовою сумою


Рівень складності Medium
Часто запитують у Амазонка GE Healthcare Google Похід
масив Мішанина Пошук Сортування

Задача «Знайти всі триплети з нульовою сумою» стверджує, що вам дано масив, що містить як позитивне, так і негативне число. Постановка задачі просить з’ясувати триплет із сумою, рівною 0.

Знайдіть усі триплети з нульовою сумою

Приклад

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

Пояснення

Це триплети, сума яких дорівнює 0.

(-2 + -1 + 3 = 0) (-2 + 0 + 2 = 0) (-1+ 0 + 1 = 0)

arr[] = {2,4,-5,-1,3}
(-5 2 3)

Пояснення

Це триплети, сума чисел яких дорівнює 0 ⇒ -5 + 2 + 3 = 0

Алгоритм

  1. сортувати заданий масив.
  2. Встановіть Boolean змінна знаходиться до помилкового.
  3. Цикл від i = 0 до i
    1. Установка ялиця = i + 1, сек = n-1 та іншу змінну x до поточного елемента масиву.
    2. Поки ялиця
      1. Перевірте, чи три елементи разом складають суму 0.
        1. Якщо true, тоді надрукуйте всі три числа та встановіть дляFound значення true.
      2. Перевірте, чи сума трьох елементів (поточних елементів масиву) не менша за 0.
        1. Якщо вірно, тоді збільште значення ялиці на 1.
      3. Перевірте ще, якщо сума трьох елементів більша за 0.
          1. Якщо true, тоді зменште значення sec на 1.
  4. Перевірте, чи isFound залишається хибним, це означає, що трійні не можуть бути утворені.

Пояснення

Нам дається масив. Потім нам пропонують визначити триплети, які можна сформувати із заданими числами в масиві, сума якого дорівнює 0. Ми збираємось використовувати вкладений цикл. Цей алгоритм може працювати в постійному просторі. Спочатку ми будемо сортувати масив. Таким чином ми можемо використовувати техніку з двома покажчиками. Ми оголосимо одну булеву змінну і спочатку встановимо для її значення значення false. Це лише для того, щоб переконатися, що ми не знайдемо жодного з триплетів, що мають елементи, що дорівнюють 0, значення знаходиться залишається помилковим. Тоді ми збираємось оновлювати його до істини, коли виявляємо триплет. Отже, з цього ми можемо зробити висновок, що триплету не знайдено.

Спочатку ми відсортуємо масив у вкладеному циклі. Потім ми переходимо масив до n-1. Ми встановимо початкове значення як i + 1, останнє значення - n-1, а x - поточне значення у зовнішньому циклі. У внутрішньому циклі ми обходимо значення масиву і перевіряємо, чи дорівнює сума всіх трьох елементів (x + arr [fir] + arr [sec]) 0 чи ні. Якщо виявиться, що воно дорівнює 0, це означає, що ми знайшли першу пару і надрукували всі поточні значення масиву, і встановили для isFound значення true.

Це вказує на те, що ми знайшли одну з пар. Якщо сума триплета не дорівнює 0. Ми перевіряємо, чи сума трьох поточних елементів менша 0. Якщо сума менше 0. Ми збільшуємо fir, означає, що наше початкове значення збільшується. Якщо умова не виконана. Ми перевіряємо, чи сума більша за 0. Якщо true, то зменшуємо сек.

Таким чином, ми збираємось знайти всі можливі триплети, які можна підсумувати до 0.

Код С ++ для пошуку всіх триплетів з нульовою сумою

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}
(-2 -1 3)
(-2 0 2)
(-1 0 1)

Код Java для пошуку всіх триплетів з нульовою сумою

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}
(-2 -1  3)
(-2 0  2)
(-1 0  1)

Аналіз складності

Складність часу

О (н.)2) де "N"  - кількість елементів у масиві. Оскільки ми використовуємо техніку з двома покажчиками, яка сприяє O (n) часу. Але сама методика використовується протягом O (n) часу. Таким чином, змушуючи алгоритм працювати за час O (n ^ 2).

Складність простору

O (1) оскільки додатковий простір не потрібен.