Znalezienie trzech elementów w tablicy, których suma jest najbliższa podanej liczbie

155

Biorąc pod uwagę tablicę liczb całkowitych, A 1 , A 2 , ..., A n , w tym ujemne i dodatnie, oraz inną liczbę całkowitą S. Teraz musimy znaleźć trzy różne liczby całkowite w tablicy, których suma jest najbliższa podanej liczbie całkowitej S Jeśli istnieje więcej niż jedno rozwiązanie, każde z nich jest w porządku.

Możesz założyć, że wszystkie liczby całkowite mieszczą się w zakresie int32_t i przy obliczaniu sumy nie nastąpi przepełnienie arytmetyczne. S to nic specjalnego, tylko losowo wybrana liczba.

Czy istnieje inny skuteczny algorytm niż wyszukiwanie siłowe do znalezienia trzech liczb całkowitych?

ZelluX
źródło
1
Jeśli szukasz sumy równej liczbie (a nie najbliższej), byłby to problem 3SUM .
Bernhard Barker

Odpowiedzi:

186

Czy istnieje inny skuteczny algorytm niż wyszukiwanie siłowe do znalezienia trzech liczb całkowitych?

Tak; można rozwiązać w O (n = 2 ) Czas! Po pierwsze, zastanów się, że problem Pmożna sformułować równoważnie w nieco inny sposób, co eliminuje potrzebę określenia „wartości docelowej”:

Oryginalny problemu P: Biorąc pod tablicę Az nliczb i wartości docelowej S, czy istnieje taka 3-krotki z Atym, że sum S?

Problem modyfikowany P': Biorąc pod tablicę Az nliczb całkowitych, czy istnieje taka 3-krotki z Atym, że kwoty do zera?

Zauważ że można przejść z tą wersją problemu P'z Podejmując swój S / 3 z każdego elementu A, ale teraz nie trzeba już wartość docelową.

Oczywiście, gdybyśmy po prostu przetestowali wszystkie możliwe 3 krotki, rozwiązalibyśmy problem w O (n 3 ) - to jest linia bazowa brutalnej siły. Czy można zrobić lepiej? A jeśli wybierzemy krotki w nieco sprytniejszy sposób?

Najpierw poświęcamy trochę czasu na posortowanie tablicy, co kosztuje nas początkową karę w wysokości O (n log n). Teraz wykonujemy ten algorytm:

for (i in 1..n-2) {
  j = i+1  // Start right after i.
  k = n    // Start at the end of the array.

  while (k >= j) {
    // We got a match! All done.
    if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])

    // We didn't match. Let's try to get a little closer:
    //   If the sum was too big, decrement k.
    //   If the sum was too small, increment j.
    (A[i] + A[j] + A[k] > 0) ? k-- : j++
  }
  // When the while-loop finishes, j and k have passed each other and there's
  // no more useful combinations that we can try with this i.
}

Algorytm ten działa poprzez umieszczenie trzy wskaźniki, i, j, i kw różnych punktach w tablicy. izaczyna się na początku i powoli dociera do końca. kwskazuje na ostatni element. jwskazuje, gdzie isię zaczęło. Iteracyjnie próbujemy zsumować elementy w ich odpowiednich indeksach i za każdym razem, gdy zachodzi jedna z poniższych sytuacji:

  • Suma jest dokładnie poprawna! Znaleźliśmy odpowiedź.
  • Suma była za mała. Zbliż jsię do końca, aby wybrać następną największą liczbę.
  • Suma była za duża. Przejdź kbliżej początku, aby wybrać następną najmniejszą liczbę.

Dla każdego iwskaźniki ji kbędą się do siebie stopniowo zbliżać. W końcu mijają się nawzajem i na tym etapie nie musimy próbować niczego innego i, ponieważ sumowalibyśmy te same elementy, tylko w innej kolejności. Następnie próbujemy następnego ii powtarzamy.

W końcu albo wyczerpimy przydatne możliwości, albo znajdziemy rozwiązanie. Widać, że jest to O (n 2 ), ponieważ wykonujemy zewnętrzną pętlę O (n) razy, a wewnętrzną pętlę wykonujemy O (n) razy. Można to zrobić pod-kwadratowo, jeśli masz naprawdę ochotę, przedstawiając każdą liczbę całkowitą jako wektor bitowy i wykonując szybką transformatę Fouriera, ale to wykracza poza zakres tej odpowiedzi.


Uwaga: ponieważ jest to pytanie do wywiadu, trochę tutaj oszukałem: ten algorytm pozwala na wielokrotny wybór tego samego elementu. Oznacza to, że (-1, -1, 2) byłoby prawidłowym rozwiązaniem, podobnie jak (0, 0, 0). Znajduje również tylko dokładne odpowiedzi, a nie najbliższą odpowiedź, jak wspomina tytuł. Jako ćwiczenie dla czytelnika, pozwolę ci dowiedzieć się, jak sprawić, by działało tylko z różnymi elementami (ale to bardzo prosta zmiana) i dokładnymi odpowiedziami (co jest również prostą zmianą).

John Feminella
źródło
8
Wygląda na to, że algorytm może znaleźć tylko 3-krotkę, która jest równa S, a nie najbliższa S.
ZelluX
7
ZelluX: Jak wspomniałem w notatce, nie chciałem dawać zbyt wiele, ponieważ jest to problem z wywiadem. Miejmy nadzieję, że możesz zobaczyć, jak go zmodyfikować, aby uzyskać najbliższą odpowiedź. (Wskazówka: jednym ze sposobów jest śledzenie najbliższej odpowiedzi do tej pory i nadpisanie jej, jeśli znajdziesz lepszą.)
John Feminella
12
co się stanie, jeśli nie zmodyfikujemy stwierdzenia problemu, zamiast tego będziemy szukać aj i ak tej sumy do ai + S.
Boolean
3
@ZelluX: To jest podobne do tego, jak działa sortowanie przez scalanie (tak to najpierw kliknęło dla mnie). To, co próbuje zrobić ta wewnętrzna pętla, to udowodnić, że A [j] lub A [k] nie może być częścią żadnego satysfakcjonującego rozwiązania. Problem w dowolnym momencie brzmi: „Czy jest jakaś para j '> = j oraz k' <= k taka, że ​​A [j] + A [k] = S - A [i]?” Patrząc na obecną parę (i, j), są 3 możliwości: suma jest huk (stop - wygraliśmy!), Jest za niska lub za wysoka. Jeśli jest za mała, to suma A [j] + A [k '] również musi być za mała dla każdego k' <= k, ponieważ w każdej takiej sumie pierwszy wyraz (A [j]) będzie taki sam. ..
j_random_hacker
1
... a drugi człon (A [k ']) będzie taki sam lub nawet niższy niż A [k]. Więc w tym przypadku udowodniliśmy, że A [j] nie może uczestniczyć w żadnej satysfakcjonującej sumie - więc równie dobrze możemy ją odrzucić! Które robimy, ustawiając j = j + 1 i zaczynając od nowa (chociaż zamiast tego może pomóc myślenie w kategoriach rekurencyjnego rozwiązania mniejszego podproblemu). Podobnie, jeśli suma A [j] + A [k] jest zbyt wysoka, to wiemy, że A [j '] + A [k] musi być również za duże dla każdego j'> = j, ponieważ A [j '] musi być co najmniej tak duże jak A [j], a my już jesteśmy za wysoko. Oznacza to, że możemy bezpiecznie odrzucić A [k], ustawiając k = k-1 i zaczynając od nowa.
j_random_hacker
28

z pewnością jest to lepsze rozwiązanie, ponieważ jest łatwiejsze do odczytania, a przez to mniej podatne na błędy. Jedynym problemem jest to, że musimy dodać kilka wierszy kodu, aby uniknąć wielokrotnego wybierania jednego elementu.

Kolejne rozwiązanie O (n ^ 2) (przy użyciu skrótu).

// K is the sum that we are looking for
for i 1..n
    int s1 = K - A[i]
    for j 1..i
        int s2 = s1 - A[j]
        if (set.contains(s2))
            print the numbers
    set.add(A[i])
Cem
źródło
8
Wadą jest przechowywanie O (N) zamiast robienia tego na miejscu.
Charles Munger
6
Używanie skrótu nie jest ścisłe O (n ^ 2), ponieważ zestaw skrótu może się zdegenerować w rzadkich przypadkach, powodując nawet liniowe czasy wyszukiwania.
Ext3h
@Charles - Również rozwiązanie Johna wymaga spacji O (N), ponieważ podczas sortowania zmieniasz oryginalną tablicę. Oznacza to, że dzwoniący może potrzebować kopii obronnej przed użyciem funkcji.
gamliela
Myślę, że w twoim algorytmie jest błąd. s2może być już wybranym elementem. Np. Jeśli tablica jest 0,1,2i Kjest 2, nie powinno być odpowiedzi. Myślę, że twój algorytm wyświetli wynik, 0,1,1co jest oczywiście niepoprawne.
Yamcha,
7

Rozwiązanie Johna Feminelli zawiera błąd.

Na linii

if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])

Musimy sprawdzić, czy i, j, k są różne. W przeciwnym razie, jeśli mój element docelowy to 6i jeśli moja tablica wejściowa zawiera {3,2,1,7,9,0,-4,6}. Jeśli wydrukuję krotki, które sumują się do 6, otrzymam również 0,0,6jako wyjście. Aby tego uniknąć, musimy w ten sposób zmodyfikować warunek.

if ((A[i] + A[j] + A[k] == 0) && (i!=j) && (i!=k) && (j!=k)) return (A[i], A[j], A[k])
Rambo7
źródło
2
Rozwiązanie Johna Feminelli polega tylko na przedstawieniu algorytmu do rozwiązania problemu, sprecyzował również, że jego rozwiązanie nie będzie działać dla warunku odrębnej liczby i musisz trochę zmodyfikować powyższy kod, który zostawił czytelnikowi.
EmptyData
3
Właściwie nigdy nie będę j, ponieważ zawsze zaczynasz ją od j = i + 1. Jedynym rzeczywistym warunkiem, który powinieneś sprawdzić, jest to, czy j == k. Jednak ustawiając pętlę while na j <k, rozwiązałeś problemy bez długiej instrukcji if, ponieważ k zawsze będzie większe niż j, a j zawsze większe niż i.
lorenzocastillo
2
Nie wydaje się to odpowiedzią na pytanie, ale raczej komentarzem do odpowiedzi Johna Feminelli.
Bernhard Barker
6

Co powiesz na coś takiego, czyli O (n ^ 2)

for(each ele in the sorted array)
{
    ele = arr[i] - YOUR_NUMBER;
    let front be the pointer to the front of the array;
    let rear be the pointer to the rear element of the array.;

    // till front is not greater than rear.                    
    while(front <= rear)
    {
        if(*front + *rear == ele)
        {
            print "Found triplet "<<*front<<","<<*rear<<","<<ele<<endl;
            break;
        }
        else
        {
            // sum is > ele, so we need to decrease the sum by decrementing rear pointer.
            if((*front + *rear) > ele)
                decrement rear pointer.
            // sum is < ele, so we need to increase the sum by incrementing the front pointer.
            else
                increment front pointer.
        }
    }

Sprawdza, czy suma 3 elementów jest dokładnie równa Twojej liczbie. Jeśli chcesz najbliżej, możesz ją zmodyfikować, aby zapamiętać najmniejszą deltę (różnicę między twoją liczbą bieżących trioli), a na końcu wydrukować trójkę odpowiadającą najmniejszej delcie.

codaddict
źródło
jeśli chcesz znaleźć k elementów, aby otrzymać sumę, jaka jest złożoność? Jak sobie z tym radzisz?
coder_15
Przy takim podejściu złożoność dla k elementów wynosi O (n ^ (k-1)) dla k> = 2. Musisz dodać zewnętrzną pętlę dla każdego dodatkowego sumy.
Ext3h
5

Zauważ, że mamy posortowaną tablicę. To rozwiązanie jest podobne do rozwiązania Johna, tylko że szuka sumy i nie powtarza tego samego elementu.

#include <stdio.h>;

int checkForSum (int arr[], int len, int sum) { //arr is sorted
    int i;
    for (i = 0; i < len ; i++) {
        int left = i + 1;
        int right = len - 1;
        while (right > left) {
            printf ("values are %d %d %d\n", arr[i], arr[left], arr[right]);
            if (arr[right] + arr[left] + arr[i] - sum == 0) {
                printf ("final values are %d %d %d\n", arr[i], arr[left], arr[right]);
                return 1;
            }
            if (arr[right] + arr[left] + arr[i] - sum > 0)
                right--;
            else
                left++;
        }
    }
    return -1;
}
int main (int argc, char **argv) {
    int arr[] = {-99, -45, -6, -5, 0, 9, 12, 16, 21, 29};
    int sum = 4;
    printf ("check for sum %d in arr is %d\n", sum, checkForSum(arr, 10, sum));
}
Pasada
źródło
Należy obliczyć bezwzględną różnicę a[r] + a[l] + a[i] - sum. Przymierz arr = [-1, 2, 1, -4] sum = 1.
Dimitry
3

Oto kod w C ++:

bool FindSumZero(int a[], int n, int& x, int& y, int& z)
{
    if (n < 3)
        return false;

    sort(a, a+n);

    for (int i = 0; i < n-2; ++i)
    {
        int j = i+1;
        int k = n-1;

        while (k >= j)
        {
            int s = a[i]+a[j]+a[k];

            if (s == 0 && i != j && j != k && k != i)
            {
                x = a[i], y = a[j], z = a[k];
                return true;
            }

            if (s > 0)
                --k;
            else
                ++j;
        }
    }

    return false;
}
Peter Lee
źródło
2

Bardzo proste rozwiązanie N ^ 2 * logN: posortuj tablicę wejściową, następnie przejdź przez wszystkie pary A i , A j (N ^ 2 razy) i dla każdej pary sprawdź, czy (S - A i - A j ) jest w tablicy ( czas logowania).

Inne rozwiązanie O (S * N) wykorzystuje klasyczne podejście do programowania dynamicznego .

W skrócie:

Utwórz dwuwymiarową macierz V [4] [S + 1]. Wypełnij w taki sposób, aby:

V [0] [0] = 1, V [0] [x] = 0;

V 1 [A i ] = 1 dla dowolnego i, V 1 [x] = 0 dla wszystkich pozostałych x

V [2] [A i + A j ] = 1, dla każdego i, j. V [2] [x] = 0 dla wszystkich pozostałych x

V [3] [suma dowolnych 3 elementów] = 1.

Aby go wypełnić, wykonaj iterację przez A i , dla każdego A i przejdź przez tablicę od prawej do lewej.

Olexiy
źródło
niewielka zmiana w pierwszym algorytmie .. jeśli element nie istnieje, to pod koniec wyszukiwania binarnego musielibyśmy spojrzeć na element po lewej, bieżący i prawy, aby zobaczyć, który daje najbliższy wynik .
Anurag
Tablica jest zbyt duża i nie jest to O (s * N). Ten krok to O (N ^ 2): V [2] [Ai + Aj] = 1, dla każdego i, j. V [2] [x] = 0 dla wszystkich pozostałych x.
Richard
1

Można to skutecznie rozwiązać w O (n log (n)) w następujący sposób. Podaję rozwiązanie, które mówi, czy suma dowolnych trzech liczb jest równa danej liczbie.

import java.util.*;
public class MainClass {
        public static void main(String[] args) {
        int[] a = {-1, 0, 1, 2, 3, 5, -4, 6};
        System.out.println(((Object) isThreeSumEqualsTarget(a, 11)).toString());
}

public static boolean isThreeSumEqualsTarget(int[] array, int targetNumber) {

    //O(n log (n))
    Arrays.sort(array);
    System.out.println(Arrays.toString(array));

    int leftIndex = 0;
    int rightIndex = array.length - 1;

    //O(n)
    while (leftIndex + 1 < rightIndex - 1) {
        //take sum of two corners
        int sum = array[leftIndex] + array[rightIndex];
        //find if the number matches exactly. Or get the closest match.
        //here i am not storing closest matches. You can do it for yourself.
        //O(log (n)) complexity
        int binarySearchClosestIndex = binarySearch(leftIndex + 1, rightIndex - 1, targetNumber - sum, array);
        //if exact match is found, we already got the answer
        if (-1 == binarySearchClosestIndex) {
            System.out.println(("combo is " + array[leftIndex] + ", " + array[rightIndex] + ", " + (targetNumber - sum)));
            return true;
        }
        //if exact match is not found, we have to decide which pointer, left or right to move inwards
        //we are here means , either we are on left end or on right end
        else {

            //we ended up searching towards start of array,i.e. we need a lesser sum , lets move inwards from right
            //we need to have a lower sum, lets decrease right index
            if (binarySearchClosestIndex == leftIndex + 1) {
                rightIndex--;
            } else if (binarySearchClosestIndex == rightIndex - 1) {
                //we need to have a higher sum, lets decrease right index
                leftIndex++;
            }
        }
    }
    return false;
}

public static int binarySearch(int start, int end, int elem, int[] array) {
    int mid = 0;
    while (start <= end) {
        mid = (start + end) >>> 1;
        if (elem < array[mid]) {
            end = mid - 1;
        } else if (elem > array[mid]) {
            start = mid + 1;
        } else {
            //exact match case
            //Suits more for this particular case to return -1
            return -1;
        }
    }
    return mid;
}
}
Raju Singh
źródło
Myślę, że to nie zadziała. To prawda, masz dwa proste przypadki, w których możesz przejść do przodu leftIndexlub rightIndexkiedy wszystkie elementy w środku są albo ściśle mniejsze, albo większe od pożądanej liczby. Ale co w przypadku, gdy wyszukiwanie binarne zatrzymało się gdzieś pośrodku? Musisz sprawdzić oba oddziały (gdzie rightIndex--i leftIndex++). W swoim rozwiązaniu po prostu ignorujesz tę sytuację. Ale nie sądzę, aby można było rozwiązać ten problem.
Aivean
0

Redukcja: myślę, że rozwiązanie @John Feminella O (n2) jest najbardziej eleganckie. Nadal możemy zredukować A [n], w którym szukać krotki. Obserwując A [k] tak, że wszystkie elementy znajdowałyby się w A [0] - A [k], gdy nasza tablica wyszukiwania jest ogromna, a SUMA (s) naprawdę małe.

Minimum [0]: - rosnąco posortowana tablica.

s = 2A [0] + A [k]: Biorąc pod uwagę s i A [], możemy znaleźć A [k] używając wyszukiwania binarnego w czasie log (n).

d1val
źródło
0

Oto program w javie, czyli O (N ^ 2)

import java.util.Stack;


public class GetTripletPair {

    /** Set a value for target sum */
    public static final int TARGET_SUM = 32;

    private Stack<Integer> stack = new Stack<Integer>();

    /** Store the sum of current elements stored in stack */
    private int sumInStack = 0;
    private int count =0 ;


    public void populateSubset(int[] data, int fromIndex, int endIndex) {

        /*
        * Check if sum of elements stored in Stack is equal to the expected
        * target sum.
        * 
        * If so, call print method to print the candidate satisfied result.
        */
        if (sumInStack == TARGET_SUM) {
            print(stack);
        }

        for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {

            if (sumInStack + data[currentIndex] <= TARGET_SUM) {
                ++count;
                stack.push(data[currentIndex]);
                sumInStack += data[currentIndex];

                /*
                * Make the currentIndex +1, and then use recursion to proceed
                * further.
                */
                populateSubset(data, currentIndex + 1, endIndex);
                --count;
                sumInStack -= (Integer) stack.pop();
            }else{
            return;
        }
        }
    }

    /**
    * Print satisfied result. i.e. 15 = 4+6+5
    */

    private void print(Stack<Integer> stack) {
        StringBuilder sb = new StringBuilder();
        sb.append(TARGET_SUM).append(" = ");
        for (Integer i : stack) {
            sb.append(i).append("+");
        }
        System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
    }

    private static final int[] DATA = {4,13,14,15,17};

    public static void main(String[] args) {
        GetAllSubsetByStack get = new GetAllSubsetByStack();
        get.populateSubset(DATA, 0, DATA.length);
    }
}
M Sach
źródło
Niezłe podejście, ale nie udało mi się dojść do punktu, w którym ograniczysz liczbę wyników do trójki. Na przykład rozważ dane wejściowe: [1,11,3,4,5,6,7,8, 2] i sumę 12, z twojego rozwiązania wynika, że ​​[1, 11] [4,8] [1,4, 5, 2] etc będą działać.
Anupam Saini,
0

Problem można rozwiązać w O (n ^ 2), rozszerzając problem sumy 2 z niewielkimi modyfikacjami: A jest wektorem zawierającym elementy, a B jest sumą wymaganą.

int Rozwiązanie :: threeSumClosest (vector & A, int B) {

sort(A.begin(),A.end());

int k=0,i,j,closest,val;int diff=INT_MAX;

while(k<A.size()-2)
{
    i=k+1;
    j=A.size()-1;

    while(i<j)
    {
        val=A[i]+A[j]+A[k];
        if(val==B) return B;
        if(abs(B-val)<diff)
        {
            diff=abs(B-val);
            closest=val;
        }
        if(B>val)
        ++i;
        if(B<val) 
        --j;
    }
    ++k;

}
return closest;
Anurag Semwal
źródło
0

Oto kod Python3

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        result = set()
        nums.sort()
        L = len(nums)     
        for i in range(L):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            for j in range(i+1,L):
                if j > i + 1 and nums[j] == nums[j-1]:
                    continue  
                l = j+1
                r = L -1
                while l <= r:
                    sum = nums[i] + nums[j] + nums[l]
                    result.add(sum)
                    l = l + 1
                    while l<=r and nums[l] == nums[l-1]:
                        l = l + 1
        result = list(result)
        min = result[0]
        for i in range(1,len(result)):
            if abs(target - result[i]) < abs(target - min):
                min = result[i]
        return min
uday reddy
źródło
-1

Inne rozwiązanie, które wcześnie sprawdza i zawodzi:

public boolean solution(int[] input) {
        int length = input.length;

        if (length < 3) {
            return false;
        }

        // x + y + z = 0  => -z = x + y
        final Set<Integer> z = new HashSet<>(length);
        int zeroCounter = 0, sum; // if they're more than 3 zeros we're done

        for (int element : input) {
            if (element < 0) {
                z.add(element);
            }

            if (element == 0) {
                ++zeroCounter;
                if (zeroCounter >= 3) {
                    return true;
                }
            }
        }

        if (z.isEmpty() || z.size() == length || (z.size() + zeroCounter == length)) {
            return false;
        } else {
            for (int x = 0; x < length; ++x) {
                for (int y = x + 1; y < length; ++y) {
                    sum = input[x] + input[y]; // will use it as inverse addition
                    if (sum < 0) {
                        continue;
                    }
                    if (z.contains(sum * -1)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

Dodałem tutaj kilka testów jednostkowych: GivenArrayReturnTrueIfThreeElementsSumZeroTest .

Jeśli zestaw zużywa zbyt dużo miejsca można łatwo używać java.util.BitSet że użyje O (n / w) przestrzeni .

moxi
źródło
-1

Program, aby uzyskać te trzy elementy. Właśnie posortowałem najpierw tablicę / listę i zaktualizowałem je na minClosenesspodstawie każdej trójki.

public int[] threeSumClosest(ArrayList<Integer> A, int B) {
    Collections.sort(A);
    int ansSum = 0;
    int ans[] = new int[3];
    int minCloseness = Integer.MAX_VALUE;
    for (int i = 0; i < A.size()-2; i++){
        int j = i+1;
        int k = A.size()-1;
        while (j < k){
            int sum = A.get(i) + A.get(j) + A.get(k);
            if (sum < B){
                j++;
            }else{
                k--;
            }
            if (minCloseness >  Math.abs(sum - B)){
                minCloseness = Math.abs(sum - B);
                ans[0] = A.get(i); ans[1] = A.get(j); ans[2] = A.get(k);
            }
        }
    }
    return ans;
}
Saurav Sahu
źródło
-2

Zrobiłem to w n ^ 3, mój pseudokod jest poniżej;

// Utwórz mapę mieszania z kluczem jako liczbą całkowitą i wartością jako ArrayList // iteruj po liście przy użyciu pętli for, dla każdej wartości na liście wykonaj iterację ponownie, zaczynając od następnej wartości;

for (int i=0; i<=arr.length-1 ; i++){
    for (int j=i+1; j<=arr.length-1;j++){

// jeśli suma arr [i] i arr [j] jest mniejsza niż żądana suma, to istnieje możliwość znalezienia trzeciej cyfry, więc wykonaj kolejną pętlę for

      if (arr[i]+arr[j] < sum){
        for (int k= j+1; k<=arr.length-1;k++)

// w tym przypadku szukamy teraz trzeciej wartości; jeśli suma arr [i] i arr [j] i arr [k] jest sumą pożądaną, to dodaj je do HashMap, tworząc klucz arr [i], a następnie dodając arr [j] i arr [k] do ArrayList w wartości tego klucza

          if (arr[i]+arr[j]+arr[k] ==  sum){              
              map.put(arr[i],new ArrayList<Integer>());
              map.get(arr[i]).add(arr[j]);
              map.get(arr[i]).add(arr[k]);}

po tym masz teraz słownik, który zawiera wszystkie wpisy reprezentujące trzy wartości dodawane do żądanej sumy. Wyodrębnij wszystkie te wpisy za pomocą funkcji HashMap. To działało doskonale.

poniżej zera
źródło