Поиск трех элементов в массиве, сумма которого ближе всего к заданному числу

Ответ 1

Есть ли какой-либо эффективный алгоритм, кроме поиска грубой силы, для поиска трех целых чисел?

Да; мы можем решить это в O (n ²) времени! Во-первых, подумайте, что ваша проблема P может быть выражена эквивалентно несколько иначе, что устраняет необходимость в "целевом значении":

исходная задача P: Учитывая массив A из n целых чисел и целевое значение S, существует ли 3-кортеж из A, который суммируется с S?

измененная проблема P': Учитывая массив A из n целых чисел, существует ли 3-кортеж из A, который суммируется с нулем?

Обратите внимание, что вы можете перейти из этой версии проблемы P' из P путем вычитания вашего S/3 из каждого элемента в A, но теперь вам больше не нужно целевое значение.

Ясно, что если мы просто проверим все возможные 3-кортежи, мы бы решили проблему в O (n ³) - что базовая линия грубой силы. Можно ли сделать лучше? Что, если мы будем выбирать кортежи несколько более умным способом?

Во-первых, мы вкладываем некоторое время на сортировку массива, что требует от нас первоначального штрафа за O (n log n). Теперь мы выполняем этот алгоритм:

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

Этот алгоритм работает путем размещения трех указателей, i, j и k в разных точках массива. i начинается с самого начала и медленно работает до конца. k указывает на самый последний элемент. j указывает на начало i. Мы итеративно пытаемся суммировать элементы по их соответствующим индексам, и каждый раз происходит одно из следующего:

• Сумма точно верна! Мы нашли ответ.
• Сумма была слишком мала. Переместите j ближе к концу, чтобы выбрать следующий самый большой номер.
• Сумма была слишком большой. Переместите k ближе к началу, чтобы выбрать следующее наименьшее число.

Для каждого i указатели j и k будут постепенно приближаться друг к другу. В конце концов они передадут друг другу, и в этот момент нам не нужно ничего пробовать для этого i, так как мы будем суммировать одни и те же элементы только в другом порядке. После этого мы попробуем следующий i и повторим.

В конце концов, мы либо исчерпаем полезные возможности, либо найдем решение. Вы можете видеть, что это O (n ²), так как мы выполняем внешний цикл O (n) раз, и мы выполняем внутренний цикл O (n) раз. Можно сделать это субквадратично, если вы действительно любите, представляя каждое целое число как бит-вектор и выполняя быстрое преобразование Фурье, но выходящее за рамки этого ответа.

Примечание.. Поскольку это вопрос интервью, я немного обманул здесь: этот алгоритм позволяет выбирать один и тот же элемент несколько раз. То есть, (-1, -1, 2) будет правильным решением, как и (0, 0, 0). Он также находит только точные ответы, а не самый близкий ответ, как упоминается в названии. В качестве упражнения для читателя я дам вам понять, как заставить его работать только с отдельными элементами (но это очень простое изменение) и точные ответы (что также является простым изменением).

Ответ 2

Конечно, это лучшее решение, потому что оно легче читать и, следовательно, менее подвержено ошибкам. Единственная проблема заключается в том, что нам нужно добавить несколько строк кода, чтобы избежать множественного выбора одного элемента.

Другое решение O (n ^ 2) (с использованием хеширования).

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

Ответ 3

Я считаю, что мы можем модифицировать @John Feminella отличный ответ на использование бинарного поиска, тем самым сокращая время выполнения до O (nlgn). Пользовательская функция binary_search (alist, value, low, high) возвращает индекс значения, если он найден, else -10, если он заканчивается с левой стороны, -20, если он заканчивается справа:

def triplet_sum(alist, total):
    alist.sort() #modifies the list in place - more efficient than sorted() but not great if we need the list unmodified
    left, right = 0, len(alist) - 1
    while right > left:
        elem = total - alist[left] - alist[right]
        mid = binary_search(alist, elem, left, right)
        if mid >= 0: #found
            return (alist[left], alist[mid], alist[right])
        elif mid == -10: #terminated left 
            right -= 1
        elif mid == -20: #terminated right
            left += 1
    return None

• Сначала отсортируйте список - время O (nlgn)
• left начинается как 0, а справа - n-1 (последний индекс)
• Двоичный поиск третьего элемента, который завершает общее время суммирования - O (logn)
• Если найдено, верните триплет
• Если двоичный поиск завершается в левой части списка, уменьшите его право
• Если двоичный поиск заканчивается в правой части, добавьте влево

В цикле while выполняется O (n) раз, каждый раз, когда выполняется O (logn), для всего O (nlogn). Дайте мне знать, если это поможет, и я хотел бы услышать любые улучшения/предложения.

Ответ 4

Как насчет того, что такое 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.
        }
    }

Это находит, если сумма из трех элементов точно равна вашему числу. Если вы хотите ближе всего, вы можете изменить его, чтобы запомнить наименьшую дельту (разницу между вашим номером текущего триплета), а в конце напечатать триплет, соответствующий наименьшей дельте.

Ответ 5

Решение Джона Фэминеллы имеет ошибку.

В строке

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

Нам нужно проверить, все ли i, j, k. В противном случае, если мой целевой элемент 6, и если мой входной массив содержит {3,2,1,7,9,0,-4,6}. Если я распечатаю кортежи, сумма которых равна 6, то я также получаю 0,0,6 в качестве вывода. Чтобы этого избежать, нам нужно изменить условие таким образом.

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

Ответ 6

Обратите внимание, что у нас есть отсортированный массив. Это решение похоже на решение Джона только на то, что оно ищет сумму и не повторяет один и тот же элемент.

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

Ответ 7

Вот код С++:

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

Ответ 8

Очень простое решение N ^ 2 * logN: сортируйте входной массив, затем пройдите через все пары A _i, A _j (N ^ 2 раз), а для каждая пара проверяет, есть ли (S - A _i - A _j) в массиве (время logN).

Другое решение O (S * N) использует классический подход динамическое программирование.

Короче:

Создайте 2-мерный массив V [4] [S + 1]. Заполните его таким образом, чтобы:

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

V 1 [A _i] = 1 для любых i, V 1 [x] = 0 для всех остальных x

V [2] [A _i + A _j] = 1 для любых i, j. V [2] [x] = 0 для всех остальных x

V [3] [сумма любых трех элементов] = 1.

Чтобы заполнить его, перейдите через A _i, для каждого A _i выполните итерацию по массиву справа налево.

Ответ 9

Это можно эффективно решить в O (n log (n)) следующим образом. Я даю решение, которое говорит, если сумма любых трех чисел равна заданному числу.

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

Ответ 10

Сокращение: я думаю, что решение @John Feminella O (n2) является самым элегантным. Мы все еще можем уменьшить A [n], в котором нужно искать кортеж. Наблюдая A [k] так, чтобы все элементы были в [0] - A [k], когда наш массив поиска огромен и SUM (s) действительно мал.

A [0] минимально: - Ascending sorted array.

s = 2A [0] + A [k]: Учитывая s и A [], мы можем найти A [k], используя двоичный поиск в log (n) времени.

Ответ 11

Другое решение, которое проверяет и не работает раньше:

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

Я добавил несколько модульных тестов здесь: GivenArrayReturnTrueIfThreeElementsSumZeroTest.

Если набор использует слишком много места, я могу легко использовать java.util.BitSet, который будет использовать O (n/w) space.

Ответ 12

Вот программа в java, которая является 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);
    }
}

Ответ 13

Задача может быть решена в O (n ^ 2) путем продолжения задачи с двумя суммами с малыми модификациями. A - вектор, содержащий элементы, а B - искомая сумма.

int Решение:: threeSumClosest (вектор & 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;

Ответ 14

Я сделал это в n ^ 3, мой псевдокод ниже;

//Создаем hashMap с ключом как Integer и значение как ArrayList // итерация по списку с использованием цикла for, для каждого значения в списке повторить снова, начиная со следующего значения;

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

//если сумма arr [i] и arr [j] меньше желаемой суммы, тогда существует возможность найти третью цифру, так что другая для цикла

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

//в этом случае мы ищем третье значение; если сумма arr [i] и arr [j], а arr [k] - желаемая сумма, то добавьте их в HashMap, сделав arr [i] ключ, а затем добавив arr [j] и arr [k] в ArrayList в значение этого ключа

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

после этого у вас теперь есть словарь, который имеет все записи, представляющие три значения, добавляя к нужной сумме. Извлеките все эти записи, используя функции HashMap. Это отлично работало.