Нахождение пары сумма в O (nlogn) времени. Пожалуйста, не говорите мне решение хэш-карты O (N) времени

Question

Пожалуйста, дайте решение в течение O (nlogn) времени. Дан случайный массив целых чисел A и число x. Найдите и распечатайте пару элементов в массиве, сумма которых равна x. Массив может содержать повторяющиеся элементы.

Пример ввода:

n = 9

элементы массива: 1 3 6 2 5 4 3 2 4

x = 7

Пример вывода:

1 6

3 4

3 4

2 5

2 5

3 4

3 4

Вот мое решение, которое работает только для уникальных элементов:

#include <bits/stdc++.h>
using namespace std;
void pairSum(int input[], int size, int x) {
  sort(input, input + size);
  int i = 0, j = size - 1, min = 0, max = 0;
  while (i < j) {
    if ((input[i] + input[j]) > x) {
      j--;
    } else if ((input[i] + input[j]) < x) {
      i++;
    } else {
      if (input[i] > input[j]) {
        min = input[i];
        max = input[j];
        i++, j--;
      } else {
        min = input[i];
        max = input[j];
        i++, j--;
      }
      cout << min << " " << max << endl;
    }
  }

Answer 1

Если я вас правильно понимаю, вы также хотите, чтобы дубликаты были напечатаны. Это требует лишь небольшого изменения вашего исходного алгоритма. Он помечен комментарием:

#include <algorithm>
#include <iostream>
#include <iterator>

template<typename It, typename value_type = typename std::iterator_traits<It>::value_type>
void pairSum(It begin, It end, const value_type& x) {
    if(begin == end) return;

    std::sort(begin, end);
    std::advance(end, -1);
    while(begin < end) {
        if(x < *begin + *end) {
            std::advance(end, -1);
        } else if(*begin + *end < x) {
            std::advance(begin, 1);
        } else {
            std::cout << *begin << " + " << *end << " = " << x << '\n';

            // Only step one iterator. If the next value is the same as the currect,
            // step that iterator.
            if(*begin == *std::next(begin, 1)) std::advance(begin, 1);
            else std::advance(end, -1);
        }
    }
}

int main() {
    std::vector<int> v{9, 1, 3, 6, 2, 5, 4, 3, 2, 4, 7};
    pairSum(v.begin(), v.end(), 10);
}

Вывод

1 + 9 = 10
3 + 7 = 10
3 + 7 = 10
4 + 6 = 10
4 + 6 = 10