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

Question

Например, мне предоставлен массив: 1, 3, 9, 6, 5, 8, 3, 4 Проблема в том, что мне нужно найти пары, сумма которых равна 9 в массиве, упомянутом выше.Однако пара не должна быть повторяющейся.Это означает, что если я уже нашел первую пару [3, 6], то вторая пара [6, 3] не принимается.

Вывод этой проблемы должен быть [1, 8] [3, 6] [5, 4] (нет [6, 3], потому что он повторяется)

Я использую Java 8Чтобы решить эту проблему.

Вот некоторые коды, которые я пробовал:

public static void printSumNine(int[] input)
{
    for (int i = 0; i < input.length - 1; i++) {
        for (int j = i + 1; j < input.length; j++) {
            if (9 - input[i] == input[j]) {
                System.out.println("[" + input[i] + ", " + input[j] + "]");
            }
        }
    }
}

Затем я помещаю этот вход в параметр int input[] = {1, 3, 9, 6, 5, 8, 3, 4};

Я ожидаю, что вывод должен быть:

[1, 8] 
[3, 6]
[5, 4]

, но мой код выдает другой вывод:

[1, 8]
[3, 6]
[6, 3]
[5, 4]

Answer 1

----- ** ОБНОВЛЕНИЕ для лучшего решения ** ------

Если вы не возражаете против порядка чисел в парах, я бы посоветовал вам использовать Setи ему нужно только O (N), чтобы выполнить задачу лучше, чем O (NlogN) в текущем решении.

Решение:

    int N = 9;
    Set<Integer> set = new HashSet<>();
    int[] input = new int[] { 1, 3, 9, 6, 5, 8, 3, 4 };

    for (int i = 0; i < input.length; i++) {
        //condition N = input[i] * 2 is for some cases such as (N = 8, and array contains 2 numbers which have same value 4)
        if (set.contains(N - input[i]) && (!set.contains(input[i]) || (N ==input[i] *2)) {
            System.out.println(input[i] + " - " + (9 - input[i]));
        }
        set.add(input[i]);
    }

Сложность Hashset.contains - O (1) пока вам просто нужно запустить 1 цикл, чтобы решить вашу проблему.

---

Я предлагаю использовать Map для удаления дубликата.

Map<Integer, Integer> usedMap

Вот моя модифицированная версия.Хотя его сложность не хорошая, но она выполнима.Я отредактирую этот пост, если найду другого подходящего с большей сложностью.

    Map<Integer, Integer> usedMap = new HashMap<Integer, Integer>();

    int[] input = new int[] { 1, 3, 9, 6, 5, 8, 3, 4 };
    for (int i = 0; i < input.length - 1; i++) {
        if (!usedMap.containsKey(input[i])) {
            for (int j = i + 1; j < input.length; j++) {
                if (!usedMap.containsKey(input[j])) {
                    if (9 - input[i] == input[j]) {
                        System.out.println("[" + input[i] + ", " + input[j] + "]");
                        usedMap.put(input[j], 1);
                    }
                }
            }
            usedMap.put(input[i], 1);
        }

    }

Answer 2

Сначала добавьте повторную проверку пар для вашего метода, такого как этот метод:

m+n=s, предположим m<n и n-m=x

m+n=m+m+x=s

x=s-2m

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

public static void printSumNine(int[] input) {
    BitSet checkPool = new BitSet(input.length);
    for (int i = 0; i < input.length - 1; i++) {
        for (int j = i + 1; j < input.length; j++) {
            if (9 - input[i] == input[j]) {
                int checkSum = Math.abs(input[i] - input[j]);
                if (!checkPool.get(checkSum)) {
                    checkPool.flip(checkSum);
                    System.out.println("[" + input[i] + ", " + input[j] + "]");
                }
            }
        }
    }
}

AОбщий метод решения этой проблемы и требует затрат nlog(n) времени и не требует другой памяти:

public static void printSumNine(int[] input, int target) {
        Arrays.sort(input);
        for (int i = 0, j = input.length - 1; i < j; ) {
            int sum = input[i] + input[j];
            if (sum == target) {
                System.out.println("[" + input[i] + ", " + input[j] + "]");
                if (input[i + 1] == input[i]) {
                    i += 2;
                } else {
                    i++;
                }
            } else if (sum > target) {
                if (input[j - 1] == input[j]) {
                    j -= 2;
                } else {
                    j--;
                }
            }
        }
    }

Answer 3

Попробуйте этот код.Я использовал хэш-карту для хранения данных.при печати я проверяю значения в hashmap перед печатью.

public static void main(String[] args) {
    int input[] = {1, 3, 9, 6, 5, 8, 3, 4};
    Map<Integer, Integer> valueMap = new HashMap<>(); 
    for (int i = 0; i < input.length - 1; i++) {
        for (int j = i + 1; j < input.length; j++) {
            if (9 - input[i] == input[j]) {
                if((valueMap.containsKey(input[i])&&valueMap.containsValue(input[j])) || (valueMap.containsKey(input[j])&&valueMap.containsValue(input[i]))) {                          
                    //these are repetitive values
                } else {
                    valueMap.put(input[i], input[j]);
                    System.out.println("[" + input[i] + ", " + input[j] + "]");
                }
            }
        }
    }
}