Три суммы проблему, используя хранилище HashMap в Java


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

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

6, 9, 9

6, 6, 12

3, 9, 12

Условия:

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

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

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

Этот вопрос был задан здесь.

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

Время выполнения: O(n2)

На GitHub

public class ThreeSum {

    static class Triplet {
        final List<Integer> triplets;

        public Triplet(int x, int y, int z) {
            triplets = Arrays.asList(x, y, z);
            Collections.sort(triplets);
        }

        @Override
        public int hashCode() {
            return Objects.hash(triplets.get(0), triplets.get(1), triplets.get(2));
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof Triplet) {

                Triplet other = (Triplet) o;
                return other.triplets.get(0) == this.triplets.get(0) &&
                        other.triplets.get(1) == this.triplets.get(1) &&
                        other.triplets.get(2) == this.triplets.get(2);
            }

            return false;
        }

        @Override
        public String toString() {
            return String.format("(%d, %d, %d)", triplets.get(0), triplets.get(1), triplets.get(2));
        }
    }

    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 triplet
        for (int currentIndex = 0; currentIndex < numbers.length; currentIndex++) {
            int complement = targetSum - numbers[currentIndex];

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

                if (currentIndex != indexes[0] && currentIndex != indexes[1]) {
                    int x = numbers[indexes[0]], y = numbers[indexes[1]];
                    triplets.add(new Triplet(x, y, numbers[currentIndex]));
                }
            }
        }

        return triplets;
    }
}


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


  • Вы храните чисел из Triplet Как List внутренне, пока вы действительно не воспользовавшись интерфейсом List'ы функциональность. Например:

    return Objects.hash(triplets.get(0), triplets.get(1), triplets.get(2));

    Почему бы не просто сделать это:

    return triplets.hashCode();

    Или, другой пример:

    return other.triplets.get(0) == this.triplets.get(0) &&
    other.triplets.get(1) == this.triplets.get(1) &&
    other.triplets.get(2) == this.triplets.get(2);

    Это можно заменить на это:

    return other.triplets.equals(this.triplets);

  • Есть проблема, я не уловил в старый вопрос, но который был уже там присутствуют: ваш код не учитывает возможности того, что такая же сумма составляет более одной пары чисел, потому что вы не просто отображение целых чисел в одной паре индексов, и если вы встретите пару, которая добавляет до суммы, которая уже хранится в lookupстарый индекс пара получает переопределен.

    Путь к преодолению этой проблемы может быть сопоставление целых чисел List<int[]>), но это может сделать вещи еще более сложным, и я думаю, что причина того, что это будет вам слишком сложной, что вы, в самом деле, жестко рекурсивный процесс (сначала необходимо создать пар, потом от пары вы создаете тройни и т. д.). Вы могли бы попробовать написать метод, который аккумулирует все возможные n-туплетов, с n быть любое произвольное положительное целое число, с помощью рекурсии, например, так:


    • Если n это 1тогда возвращать массив/список всех целых чисел

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

    Я представляю, что это будет гораздо легче, чем то, что вы в настоящее время (может, это тоже, что вы подразумеваете под свой код, "мутной"), а также гораздо более гибким. Правда, если это просто пар, тогда это может быть не так быстро, как то, что вы сделали здесь, но если дело доходит до туплетов более чем на 2 цифры, я не думаю, что есть много пользы от того, что вы пытаетесь сделать здесь (хотя это только предположение, на самом деле я не протестировать).


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

Ваш код является довольно неэффективным путем сохранения всех сумм пар в HashMap.

Требования к памяти растут в геометрической прогрессии (добавление элемента массива из N добавляет N пар, поэтому он растет в факториал порядке).

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

Это наиболее легко сделано рекурсивно. У вас есть набор чисел, а на следующий число вы можете включить в свой набор или нет. Повторите это рекурсивно.

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

public class Recurse {
static final int target = 24;
static final int sumCount = 3;
ArrayList<int[]> solutions = new ArrayList<int[]>();

public void sum(int arr[], int arrayIndex, int sum, int indicesSoFar[]) {
//you can either include the current value or not

//first we try skipping it
if(indicesSoFar.length + arr.length - (arrayIndex + 1) >= sumCount) { //only skip if there are enough numbers left
sum(arr, arrayIndex + 1, sum, indicesSoFar);
}
//now we try using it
int val = arr[arrayIndex];
int added = val + sum;
if(indicesSoFar.length + 1 == sumCount) {//if we use it, it is the last in the set
if(added == target) {// the sum matches, so it is a solution
int next[] = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
next[indicesSoFar.length] = arrayIndex;
solutions.add(next);
}
} else if(added <= target) {//use it if we can (the sum is not too large). This assumes all array values are positive, if negative values allowed, then remove the "if(added <= target)" condition
int next[] = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
next[indicesSoFar.length] = arrayIndex;
sum(arr, arrayIndex + 1, added, next);
}
}

public static void main(String args[]) {
new Recurse().sum(new int[] {12, 3, 4, 1, 6, 9}, 0, 0, new int[0]);
}
}

Это все, что вам нужно, когда вы используете рекурсивный подход. Если вы добавляете код, чтобы распечатать результаты, как показано ниже:

public static void main(String args[]) {
Recurse recurse = new Recurse();
int arr[] = new int[] {12, 3, 4, 1, 6, 9};
recurse.sum(arr, 0, 0, new int[0]);
for(int solution[] : recurse.solutions) {
StringBuilder vals = new StringBuilder();
StringBuilder indices = new StringBuilder();
for(int index : solution) {
if(vals.length() > 0) {
indices.append(", ");
vals.append(" + ");
}
indices.append("arr[").append(index).append("]");
vals.append(arr[index]);
}
System.out.println("Solution: " + indices + "; " + vals);
}
}

Затем он дает вам:

Solution: arr[0], arr[1], arr[5] 12 + 3 + 9

Теперь, в соответствии с вашими требованиями вы не хотите несколько значений, но мне не понятно если вы говорите только о том, чтобы не использовать тот же элемент массива больше, чем один раз (т. е.[I] может появиться только один раз для каждого I в каждом растворе) или вы говорите, используя тот же номер более чем один раз (т. е. число X может появиться только один раз в каждом решении), или вы говорите, используя тот же набор добавлен более одного раза (решение X,Y и Z могут появиться только один раз). Если вы хотите обрабатывать в других случаях, например, чтобы не допустить решения с повторяющимися значениями, то просто проверить существующие решения, прежде чем добавить другой. С помощью поиска HashSet идеально подходит для этого:

public class Recurse {
static final int target = 24;
static final int sumCount = 3;
ArrayList<int[]> solutions = new ArrayList<int[]>();
ArrayList<int[]> duplicates = new ArrayList<int[]>();
HashSet<ArrayList<Integer>> solutionSet = new HashSet<ArrayList<Integer>>();

public void sum(int arr[], int arrayIndex, int sum, int indicesSoFar[]) {
//you can either include the current value or not

//first we try skipping it
if(indicesSoFar.length + arr.length - (arrayIndex + 1) >= sumCount) { //only skip if there are enough numbers left
sum(arr, arrayIndex + 1, sum, indicesSoFar);
}
//now we try using it
int val = arr[arrayIndex];
int added = val + sum;
if(indicesSoFar.length + 1 == sumCount) {//if we use it, it is the last
if(added == target) {
int next[] = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
next[indicesSoFar.length] = arrayIndex;
ArrayList<Integer> solution = new ArrayList<Integer>();
for(int i : next) {
solution.add(arr[i]);
}
Collections.sort(solution);
if(!solutionSet.contains(solution)) {
solutionSet.add(solution);
solutions.add(next);
} else {
duplicates.add(next);
}
}
} else if(added <= target) {//this assumes all array values are positive, if negative allowed, then no "if(added < target)" here
int next[] = Arrays.copyOf(indicesSoFar, indicesSoFar.length + 1);
next[indicesSoFar.length] = arrayIndex;
sum(arr, arrayIndex + 1, added, next);
}
}

public static void main2(String args[]) {
new Recurse().sum(new int[] {12, 3, 4, 1, 6, 9}, 0, 0, new int[0]);
}

public static void main(String args[]) {
Recurse recurse = new Recurse();
int arr[] = new int[] {12, 3, 4, 1, 6, 3, 9};
recurse.sum(arr, 0, 0, new int[0]);
for(int i = 0; i < 2; i++) {
String label = i == 0 ? "Solution: " : "Duplicate: ";
ArrayList<int[]> solutionList = i == 0 ? recurse.solutions : recurse.duplicates;
for(int solution[] : solutionList) {
StringBuilder vals = new StringBuilder();
StringBuilder indices = new StringBuilder();
for(int index : solution) {
if(vals.length() > 0) {
indices.append(", ");
vals.append(" + ");
}
indices.append("arr[").append(index).append("]");
vals.append(arr[index]);
}
System.out.println(label + indices + "; " + vals);
}
}
}
}

Что дает:

Solution: arr[0], arr[5], arr[6]; 12 + 3 + 9
Duplicate: arr[0], arr[1], arr[6]; 12 + 3 + 9

-1
ответ дан 2 апреля 2018 в 04:04 Источник Поделиться