Сумма пар в массиве

Question

У меня есть массив целых чисел, говорит [17, 1, 20, 4, 12, 9] Я хочу получить всю пару, сумма которой равна 21. например, в данном массиве вывод должен быть таким:

17,4
1,20
12,9

Я мог бы добиться того же, используя две петли. Но сложность идет N ^ 2. Есть ли эффективный способ сделать это.

Answer 1

Вот часть решения, использующего python 3.0 +.

Вы можете сделать это в O (N) , используя структуру данных значения пары ключей, то есть словарь.

Подход:

1. L oop один раз через массив и проверьте, вычитается ли результат значения k из текущего элемента, т.е. (k-arr [i ]) присутствует в словаре означает, что сумма результирующего значения k-arr [i] и текущего элемента arr [i] равна k. Добавьте эти два в словарь.

2. Если k-arr [i] отсутствует в словаре, добавьте ключ arr [i] со значением k-arr [i] .

3. Вы также можете добавить проверку того, что текущий элемент arr [i] больше k.

    def getPair(arr, k, dict):
        for i in range(len(arr)):
            if k - arr[i] in dict.keys():
                pass
                #print(arr[i], " ", (k-arr[i]))
            else:
                if k > arr[i]:
                    dict[arr[i]] = (k-arr[i])
   
    arr = [17, 1, 20, 4, 12, 9, 23]
    dict = {}
    getPair(arr, 21, dict)
    print("result: " , dict)
   

Answer 2

Вот фрагмент рабочего кода с вашим примером, используя HashSet:

import java.util.*;

public class Main{
    public static void main(String[] args) {
        int[] arr = new int[]{17, 1, 20, 4, 12, 9};
        HashSet<Integer> hash = new HashSet<Integer>(); 
        int sum = 21;
        
        for(int i = 0; i < arr.length; i++){
            hash.add(arr[i]);
        }
        
        for(int i = 0; i < arr.length; i++){
            if(hash.contains(sum - arr[i])){
                System.out.println(arr[i] + " and " + (sum - arr[i]));
                hash.remove(arr[i]);
            }
        }
    }
}

Сложность O (n) . Идея состоит в том, чтобы добавить все числа массива в HashSet. Затем выполните итерацию по массиву и проверьте, есть ли для каждого элемента arr[i], sum - arr[i] в HashSet. Если это так, это означает, что у вас есть совпадающая пара, поэтому вы удалите один из элементов пары, чтобы избежать повторения совпадений.

Answer 3

Используйте HashSet.

Например, поместите все элементы в HashSet (одиночный l oop, O (N)).

Затем выполните итерацию по элементы снова, и для каждого элемента i проверьте, содержит ли HashSet 21-i. Это также займет O (N).

Вы можете дополнительно оптимизировать и выполнить оба шага за один l oop, но это не изменит время работы asymptoti c O (N).

Set<Integer> set = new HashSet<>();
for (int i=0;i<arr.length;i++) {
    if (set.contains(21 - arr[i])) {
        System.out.println(arr[i] + ", " + (21 - arr[i]));
    }
    set.add (arr[i]);
}