Найти все пары чисел в массиве, сумма заданного числа без использования этого HashMap


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

вход: {-2, -1, -1, 5, 7, 7, 7, 7, 8}целевые = 7

выход: (-1, 8)

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

На GitHub

public class TwoSumProblemUsingBinarySearch {

    public static class Pair {

        private final int x;
        private final int y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = 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 static Set<Pair> findAllParis(int input[], int target) {
        int numbers[] = Arrays.copyOf(input, input.length);
        Set<Pair> pairs = new HashSet<>();

        Arrays.sort(numbers);

        for (int low = 0, high = input.length - 1; low < high; ) {
            int sum = input[low] + input[high];

            if (sum > target) {
                high--;
            } else if (sum < target) {
                low++;
            } else {
                pairs.add(new Pair(input[low], input[high]));
                high--;
                low++;
            }
        }

        return pairs;
    }
}

@Test
public void findAllParis() throws Exception {

    System.out.println(TwoSumProblemUsingBinarySearch.findAllParis(new int[]{-2, -1, -1, 5, 7, 7, 7, 7, 8}, 7));
    assertEquals(1, TwoSumProblemUsingBinarySearch.findAllParis(new int[]{-2, -1, -1, 5, 7, 7, 7, 7, 8}, 7).size());
}


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


Включение обратных связей, вот ответ

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

public class TwoSumProblemUsingBinarySearch {

public static class Pair {
private final int x;
private final int y;

public Pair(int x, int y) {
this.x = x;
this.y = 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 static Set<Pair> findAllPairs(int input[], int target) {
int numbers[] = Arrays.copyOf(input, input.length);
Set<Pair> pairs = new HashSet<>();

Arrays.sort(numbers);

for (int low = 0, high = numbers.length - 1; low < high; ) {
int sum = numbers[low] + numbers[high];

if (sum > target) {
high--;
} else if (sum < target) {
low++;
} else {
pairs.add(new Pair(input[low], input[high]));
high--;
low++;
}
}

return pairs;
}
}

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


  1. Опечатка в имени метода как указал @поскупились. Должно быть findAllPairs.

  2. Связи c неправильным массив: Вы читаете значения из input вместо отсортированный копия numbers. Это, наверное, опечатка. Е. Г. int sum = input[low] + input[high]; должно быть int sum = numbers[low] + numbers[high];

  3. Ваш for петля имеет пустой инструкции Update, в этом нет ничего плохого на SE, но немного необычно. Рассмотрим альтернативы с помощью while вместо:

    int low = 0, high = numbers.length-1;
    while (low < high) {
    int sum = numbers[low] + numbers[high];
    //...
    }

  4. Недостаточная тест: о чем свидетельствует его неспособность поймать баг в 2. тест слишком ограничены, чтобы иметь большую помощь. Рассмотрим проверки более чем один из примеров (особенно угловые-такие случаи, как пустой входной массив) и проверять на ожидаемые результаты, а не только его размер.

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

Вы можете предотвратить повторяющиеся пары, увеличение/уменьшение счетчики не только после, но пока они указывают на число, большее/меньшее, чем количество ранее они указывали на. Таким образом, вы можете хранить пары в List вместо Set, который, вероятно, будет быстрее, потому что List не нужно проверить, нет ли уже в паре, что равняется одному добавляются.

Кроме того, есть опечатка в вашем методе именами findAllParis.

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

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

            pairs.add(new Pair(input[low], input[high]));
high--;
low++;

тогда становится

            pairs.add(new Pair(numbers[low], numbers[high]));
for (final int n = numbers[high--]; low < high && numbers[high] == n; --high)
;
for (final int n = numbers[low++]; low < high && numbers[low] == n; ++low)
;

И тогда мы можем использовать простой список, а не набор:

public static List<Pair> findAllPairs(int input[], int target) {
int numbers[] = Arrays.copyOf(input, input.length);
Arrays.sort(numbers);

ArrayList<Pair> pairs = new ArrayList<>();
for (int low = 0, high = input.length - 1; low < high; ) {
int sum = numbers[low] + numbers[high];

if (sum > target) {
--high;
} else if (sum < target) {
++low;
} else {
pairs.add(new Pair(numbers[low], numbers[high]));
for (final int n = numbers[high--]; low < high && numbers[high] == n; --high)
;
for (final int n = numbers[low++]; low < high && numbers[low] == n; ++low)
;
}
}

return pairs;
}

0
ответ дан 12 сентября 2018 в 04:09 Источник Поделиться

Вы также должны добавить это findAllPairs метод для сортировки исходного списка, который является вход:

Arrays.sort(input);

-3
ответ дан 1 августа 2018 в 11:08 Источник Поделиться