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

Biorąc pod uwagę tablicę liczb całkowitych, A ₁ , A ₂ , ..., 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?

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

Tak; można rozwiązać w O (n = ² ) 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 ³ ) - 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 ² ), 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ą).

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])

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])

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.

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));
}

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;
}

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.

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;
}
}

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).

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);
    }
}

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;

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

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 .

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;
}

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.