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

Question

Дан массив целых чисел, A ₁ , A ₂ , ..., A _n , включая негативы и позитивы, и еще одно целое число S. Теперь нам нужно найти три различных целых числа в массиве, сумма которых ближе всего к данному целому числу S. Если существует более одного решения, любое из них в порядке.

Можно предположить, что все целые числа находятся в диапазоне int32_t, и при вычислении суммы не произойдет арифметического переполнения. S - это не что иное, как случайно выбранное число.

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

Answer 1

Я сделал это в п ^ 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. Это сработало отлично.

Answer 2

Еще одно решение, которое проверяет и дает сбой раньше:

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) пробел .

Answer 3

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

A [0] - минимум: - отсортированный по возрастанию массив.

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