Найти все тройняшки в массиве, которые складываются в определенную сумму


Дан массив и значение, найти все тройки в массиве, сумма которых равна заданному значению. Например, если данный массив {12, 3, 4, 1, 6, 9} и данная сумма 24тогда это одна тройня (12, 3 and 9) что способствует общую сумму 24.

Решение для данного примера:

6, 9, 9

6, 6, 12

3, 9, 12

На заказ номера в растворе не имеет значения.

Дубликат триплет не допускается.

Ряд не может быть использована несколько раз.

Вот мой код:

package kata.array;

import java.util.*;

public class ThreeSum {

  static class Triplet {
        int x, y, z;

        public Triplet(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y, z);
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof Triplet) {
                Set<Integer> numbers = new HashSet<>();
                numbers.addAll(new ArrayList<>(Arrays.asList(x, y, z)));

                Triplet other = (Triplet) o;
                return numbers.containsAll(new ArrayList<>(Arrays.asList(other.x, other.y, other.z)));
            }

            return false;
        }
    }

    public static Set<Triplet> findTriplets(int numbers[], int targetSum) {
        Set<Triplet> triplets = new HashSet<>();

        // insert all pairs in the look up table
        Map<Integer, int[]> lookup = new HashMap<>();
        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                int total = numbers[i] + numbers[j];
                lookup.put(total, new int[]{i, j});
            }
        }

        // look for the complement, if found viola! here you go with the matching triplet
        for (int number : numbers) {
            int complement = targetSum - number;

            if (lookup.containsKey(complement)) {
                int indexes[] = lookup.get(complement);
                int x = numbers[indexes[0]], y = numbers[indexes[1]];
                triplets.add(new Triplet(x, y, number));
            }
        }

        return triplets;
    }
}

Для выполнения этого кода:

public void findTriplets() throws Exception {
    int numbers[] = {12, 3, 4, 1, 6, 9};

    System.out.print(ThreeSum.findTriplets(numbers, 24));

    for (ThreeSum.Triplet triplet : ThreeSum.findTriplets(numbers, 24)) {
        System.out.println(triplet.x + ", " + triplet.y + ", " + triplet.z);
    }

    // can handle duplicate?
    System.out.println("==============================");
    numbers = new int[] {12, 3, 4, 1, 6, 9, 9, 9, 9, 9};

    System.out.print(ThreeSum.findTriplets(numbers, 24));

    for (ThreeSum.Triplet triplet : ThreeSum.findTriplets(numbers, 24)) {
        System.out.println(triplet.x + ", " + triplet.y + ", " + triplet.z);
    }
}

На GitHub



Комментарии
3 ответа


  • Triplet.hashCode() и Triplet.equals(Object) не совместимы друг с другом. Triplet.hashCode() считает орден Трех целых чисел, при Triplet.equals(Object) нет. Судя по сложности метод Triplet.equals(Object)Я предполагаю, что вы намереваетесь порядок чисел не учитывается. Способ сделать это было бы для сортировки целых чисел в метод hashCode() перед вычислением хэша.

  • В самом деле, Triplet.equals(Object) само сломалось. Подумайте: если мы определяем Triplet a = new Triplet(1,2,3) и Triplet b = new Triplet(1,1,1)тогда a.equals(b) вернется trueно b.equals(a) вернется false.

  • Независимо от вышесказанного, вы создаете ненужные Listв Triplet.equals(Object):

    numbers.addAll(new ArrayList<>(Arrays.asList(x, y, z)));

    Здесь, явное создание ArrayList из содержания List возвращенный вызов Arrays.asList(T... a) избыточна – следующим будет достаточно:

    numbers.addAll(Arrays.asList(x, y, z));

    То же самое относится к процессу преобразования элементов other к List. Можно даже обойти создание промежуточного List полностью с помощью потока:

    Set<Integer> numbers = Stream.of(x,y,z).collect(Collectors.toSet());

    Но это не собирается, чтобы помочь вам в любом случае, потому что если у вас есть две тройни как {1,1,2} и {1,2,2}тогда Setы бесполезны для сравнения две тройни.

    Самый простой способ пойти об этом, наверное, как и в методе hashCode()для сортировки целых чисел из тройняшек качестве List а потом сравнить два Listдля равенства. Фактически, вы могли уже вроде целое число в Tripletс конструктором, который будет гарантировать, что вы только когда-либо сортировка трех целых Triplet один раз. Правда, это не сохранить порядок чисел, а потом, это не действительно необходимо для целей данной программы.


  • Ваш код не выполняется в таких сценариях, как в следующем: если входной массив {5, -5, 7} а целевая сумма 5тогда ваш код будет приносить несуществующей тройни [5, -5, 5], потому что он подсчитывает число 5 дважды.

1
ответ дан 25 марта 2018 в 12:03 Источник Поделиться

Arrays.asList(other.x, other.y, other.z) уже возвращает новый список. Нет необходимости, чтобы добавить результат в Новый ArrayList вы могли бы просто использовать

numbers.containsAll(Arrays.asList(other.x, other.y, other.z));

Вы создаете ненужные объекты, которые все еще должны быть очищены сборщиком мусора. например: это может сэкономить вам памяти. Вместо:

numbers.addAll(new ArrayList<>(Arrays.asList(x, y, z)));

использовать

numbers.add(x);
numbers.add(y);
numbers.add(z);

Здесь вы можете сохранить один поиск в HashMap. Вместо:

if (lookup.containsKey(complement)) {
int indexes[] = lookup.get(complement);
...

вы можете написать:

int indexes[] = lookup.get(complement);
if (indexes != null) {
...

1
ответ дан 25 марта 2018 в 11:03 Источник Поделиться

Вот мои 2 цента:

Причина, почему вы пришли с двух различных решений: ваш ум установлен на процессуальные решения, является преждевременной оптимизацией.

Прямой вперед решение для "сумма двух проблема" будет такой:


  1. построить все возможные пары

  2. удалить дубликаты

  3. рассчитать сумму

  4. добавить в результате, если сумма совпадает

"Сумма трех" проблема только в шаге 1. и Шаг 3. (где три шага легко может быть получен для работы с любым количеством элементов).

Так вот как я сделал эту задачу:

сумма двух

public class TwoSumProblemUsingBinarySearch {

public static class Pair {

private final int x;
private final int y;

public Pair(int x, int y) {
this.x = Math.min(x, y);
this.y = Math.max(x, y);
}

@Override
public int hashCode() {
return Objects.hash(x, y);
}

@Override
public boolean equals(Object other) {
if (other instanceof Pair) {
Pair o = (Pair) other;
return this.x == o.x && this.y == o.y;
}

return false;
}

@Override
public String toString() {
return String.format("(%d, %d)", x, y);
}

public boolean hasSumOf(int target) {
return target == x + y;
}

}

public static Set<Pair> findAllParis(int input[], int target) {
Set<Pair> pairs = createDistinctPairsFromInput(input);
return removePairsNotMatchingTarget(target, pairs);
}

private static Set<Pair> createDistinctPairsFromInput(int[] input) {
Set<Pair> pairs = new HashSet<>();
for (int x : input) {
for (int y : input) {
pairs.add(new Pair(x, y));
}
}
return pairs;
}

private static Set<Pair> removePairsNotMatchingTarget(int target, Set<Pair> pairs) {
return pairs.stream().filter(p -> p.hasSumOf(target)).collect(Collectors.toSet());
}
}

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

сумма трех

Что нам нужно изменить, чтобы принять предыдущее решение "сумма двух" решение "сумма трех"?


  • нужно менять класс на пары в 3 (или более) значений

  • нам нужно добавить следующий командлет foreach петли в паре заводским методом

Итак, давайте сначала изменить Pair класс:

public static class Pair {

private final List<Integer> numbers =new ArrayList<>();

public Pair(int... y) {
for (int i : y) {
numbers.add(i);
}
Collections.sort(numbers);
}

@Override
public int hashCode() {
return Objects.hash(numbers);
}

@Override
public boolean equals(Object other) {
if (other instanceof Pair) {
Pair o = (Pair) other;
return this.numbers.size() == o.numbers.size() && this.numbers.containsAll(o.numbers);
}
return false;
}

@Override
public String toString() {
return String.format("(%s)", numbers.stream()
.map(i -> i.toString())
.collect(Collectors.joining(", ")));
}

public boolean hasSumOf(int target) {
return target == numbers.stream().mapToInt(i->i).sum();
}

}

Это все еще проходит тестовый случай для "сумма двух проблем".

И теперь мы меняем Pair создание способ принять новое требование:

private static Set<Pair> createDistinctPairsFromInput(int[] input) {
Set<Pair> pairs = new HashSet<>();
for (int x : input) {
for (int y : input) {
for (int z : input) {
pairs.add(new Pair(x, y, z));
}
}
}
return pairs;
}

Теперь у нас есть аналогичные решения на подобные проблемы. Мы могли бы даже пойти дальше и превратить фабрику способ для пары, чтобы быть параметризованы так, что же раствор может быть использован для всех "найти комбинации с подходящей суммой" проблемы.

заключение

Мой подход полностью сосредоточился на этой проблеме. Никакой оптимизации или "хитрые трюки" были использованы. Что позволило мне легко продлить первый подход более общий вариант решения аналогичных проблем.

0
ответ дан 25 марта 2018 в 01:03 Источник Поделиться