Избегание дублирования при сравнении элементов массива

Question

Вопрос в том, что: Пройдите через массив и найдите пары элементов, которые составляют определенную сумму k.

for (auto i : array) { 
    for (auto j : array) { 
     if (i+j==k) { 
      *Do something 
     } 
    } 
} 

Скажем, у нас было array = [1,2,5] и k=3; when i=1 and j=2, мы бы выполнить команду Сделайте что-нибудь. Но когда i=2 и j=1, мы выполнили бы . Повторите что-нибудь, хотя мы уже нашли 2 элемента, и мы будем повторять ответ.

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

Answer 1

Вы можете поместить результаты i + j в vector, затем sort it и затем remove duplicates, и, наконец, перейти на вектор и «сделать что-то».

Answer 2

Если заказ не имеет значения, тогда определите, какая половина всех пар вы хотите: тот, где i >= j, или тот, где i <= j.

for (i=0...) 
    for (j=i...) 

---

Как RICi отметил, что это очень медленный алгоритм (O(N^2)) по сравнению с сортировкой (копию) вектора. Я думаю, что после этого вы могли бы перебирать i с начала и j назад с конца, сравнивая i+j <= k, чтобы решить, следует ли изменять i или j далее.

Answer 3

Если у меня есть не, то ваш вопрос будет неправильным, поэтому эта объясненная процедура может быть способом ее решения.

1. Сортировать ваш массив в увеличении порядка (Предпочтительно слияния рода, потому что он принимает O (n.log (п)) времени).
2. Теперь возьмите два индекса позволяет называть их низкого и высокой, где низким является индекс к левому самому маленькой числа отсортированного массива и высоким является индексом к самим правому крупнейшему числа тот же отсортированный массив.

3. Теперь, сделайте так:

   while(low < high) { 
       if(arr[low] + arr[high] == k) { 
        print "unique pair found" 
        high = high - 1; 
        low = low + 1; 
       } 
   
       else if(arr[low] + arr[high] > k){ 
        high = high - 1;  
       } 
   
       else { 
        low = low + 1; 
       } 
   } 
   

4. Это временная сложность составляет O (N), это, безусловно, даст то, что вы ищете? (Любой сомнения очень приветствуется).