Вернуть все пары из списка целых чисел, которое вносит свой вклад в данную сумму


Дан список целых чисел возвращает все пары, которые до данного целевую сумму.

вход: {2, 7, 11, 15, -2} целевая сумма: 9

Это должно вернуть все пары я.Е {-2,11} and {7,2}.

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

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

   public class TwoSum {
    static class Pair {
        int x, y;

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

        @Override
        public boolean equals(Object o) {
            if (o == null) {
                return false;
            }

            if (o instanceof Pair) {
                Pair other = (Pair) o;
                if (other.x == this.x && other.y == this.y) {
                    return true;
                }
            }
            return false;
        }

        @Override
        public String toString() {
            return new StringBuilder().append("{").append(this.x).append(",").append(this.y).append("}").toString();
        }
    }

    public static Set<Pair> findPairs(int inputs[], int targetSum) {
        Set<Pair> results = new HashSet<>();
        Map<Integer, Integer> map = new HashMap<>();

        for (int number : inputs) {
            int remainingSum = targetSum - number;

            if (map.containsKey(number)) {
                results.add(new Pair(number, map.get(number)));
            } else {
                map.put(remainingSum, number);
            }
        }
        return results;
    }

Чтобы вызвать этот код:

System.out.println(TwoSum.findPairs(new int[]{2, 7, 11, 15, -2}, 9));

Это будет печатать:

[{-2,11}, {7,2}]

Код здесь:

https://github.com/Ramblers-Code/CodeKata/blob/master/src/main/java/kata/array/TwoSum.java



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

С учетом этих замечаний, вот ответ:

Гитхаб: https://github.com/Ramblers-Code/CodeKata/blob/master/src/main/java/kata/array/TwoSum.java#L8

static class Pair {
final int x, y;

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

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

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

@Override
public String toString() {
return new StringBuilder("{").append(this.x).append(",").append(this.y).append("}").toString();
}
}

public static Set<Pair> findPairs(int inputs[], int targetSum) {
Set<Pair> results = new HashSet<>();
Set<Integer> visited = new HashSet<>();

for (int number : inputs) {
int complement = targetSum - number;

if (visited.contains(number)) {
results.add(new Pair(number, complement));
} else {

visited.add(complement);
}
}
return results;
}

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


  • Я вижу, что вы не переопределение Object.equals(Object) без переопределения Object.hashCode(). Делая это, вы нарушаете договор Object.hashCode() (см. Последний абзац в описании Object.equals(Object)). В самом деле, HashSet<Pair> созданные в findPairs метод может не работать должным образом из-за этого.

  • Поскольку значения x и y из Pair экземпляр никогда не меняются, вы могли бы сделать x и y final, тем самым делая Pair неизменяемый класс и предотвращая случайное изменение значений x и y.

  • Я не знаю, если вы думали об этом, но ваш код будет лечить {2,3} и {3,2} как две отдельные пары. Из-за как findPairs метод работает, это не имеет значения, поскольку он никогда не создаст две пары, которые отличаются только порядком следования слагаемых, но я думал, я хотел бы указать на это в случае, если вы были не в курсе.

  • Нулевой чек в Pair.equals(Object) является излишним, поскольку null instanceof XС X быть имя класса, будет всегда возвращаться false.

  • if (o instanceof Pair) {
    Pair other = (Pair) o;
    if (other.x == this.x && other.y == this.y) {
    return true;
    }
    }
    return false;

    можно написать более лаконично, как:

    if (o instanceof Pair) {
    Pair other = (Pair) o;
    return other.x == this.x && other.y == this.y;
    }
    return false;

  • new StringBuilder().append("{")

    также может быть сокращен:

    new StringBuilder("{")

  • Вы на самом деле не нужен Map<Integer, Integer> в findPairs. Отображение чисел с их дополнением служит никакой цели, потому что состав целого числа можно вычислить путем вычитания из суммы. А Set<Integer> хватило бы, так как вы просто использовать карту, чтобы определить, является ли дополнение ряда уже появилась в последовательность чисел. Так findPairs может быть переписана в виде:

    public static Set<Pair> findPairs(int inputs[], int targetSum) {
    Set<Pair> results = new HashSet<>();
    Set<Integer> pastNumbers = new HashSet<>();

    for (int number : inputs) {
    int remainingSum = targetSum - number;

    if (pastNumbers.contains(remainingSum)) {
    results.add(new Pair(number, remainingSum));
    } else {
    pastNumbers.add(number);
    }
    }
    return results;
    }


2
ответ дан 21 марта 2018 в 02:03 Источник Поделиться

Как скупы говорит ваш Pair следует сделать x и y final и override hashCode(). Также StringBuilder в toString() это перебор ... это трудно читать и не получить ничего в производительности по сравнению с простой конкатенацией (компилятор заменит простой конкатенации с StringBuilder в любом случае). В этом случае я мог бы даже использовать String.format. (Если вы начинаете с простой конкатенацией, вашей IDE, скорее всего, предлагают быстро исправить.)

Когда вы перебираете во множественном числе, Конвенции для переменной цикла, чтобы быть в единственном числе. Так inputs inputне number.

Прямо сейчас remainingSum используется только в else случай, который предполагает, что это должно быть внутри else блок-но читаем дальше:

Это не совсем понятно, что означает эта карта; рассмотреть более осмысленное имя переменной, чем map. (На самом деле, это так непонятно, это даже не очевидно на первый взгляд, является ли код правильный. Вы должны почти никогда не название карты mapнабор setи т. д.)

Скупой это, наверное, правильно, что вам даже не очень хочется/нужна карта, просто набор, который (если вы собираетесь использовать его так, как вы используете карту) я бы назвал что-то вроде expected. Кроме того, remainingSum это не сумма, а должно быть что-то вроде complement.

Что до:

Set<Pair> results = new HashSet<>();
Set<Integer> expected = new HashSet<>();

for (int input : inputs) {
int complement = targetSum - input;

if (expected.contains(input)) {
results.add(new Pair(input, complement));
} else {
expected.add(complement);
}
}
return results;

- так что теперь у нас есть повод для complement (ранее remainingSum), чтобы быть вне if/else блок.

Лично я думаю, что алгоритм все еще немного мутный и трудно объяснить, и это было бы более понятно, если, как в скупой версии, сохранены посетили чисел (inputранее number) вместо цифры-что-бы-указать-на-успех-если-мы-должны-посетить их позже (complementранее remainingSum).

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