Вы можете сделать это за O (n ^ 2). Отлично работает с повторяющимися и отрицательными числами.

edit , как заметил Андре в комментарии, время исчисляется с использованием хэша, который имеет «худший случай» (хотя это менее вероятно, чем выигрыш в лотерее). Но вы также можете заменить хеш-таблицу сбалансированным деревом (TreeMap в java) и получить гарантированно стабильное решение O (n ^ 2 * log (n)).

Hashtable sums будет хранить все возможные суммы двух разных элементов. Для каждой суммы S он возвращает пару индексов i и j , так что a [i] + a [j] == S и i! = j . Но изначально он пуст, будем заполнять его по ходу.

for (int i = 0; i < n; ++i) {
    // 'sums' hastable holds all possible sums a[k] + a[l]
    // where k and l are both less than i

    for (int j = i + 1; j < n; ++j) {
        int current = a[i] + a[j];
        int rest = X - current;
        // Now we need to find if there're different numbers k and l
        // such that a[k] + a[l] == rest and k < i and l < i
        // but we have 'sums' hashtable prepared for that
        if (sums[rest] != null) {
            // found it
        }
    }

    // now let's put in 'sums' hashtable all possible sums
    // a[i] + a[k] where k < i
    for (int k = 0; k < i; ++k) {
        sums[a[i] + a[k]] = pair(i, k);
    }
}

Скажем, X = a [1] + a [3] + a [7] + a [10] . Эта сумма будет найдена, когда i = 7 , j = 10 и rest = a [1] + a [3] (индексы 1 и 3 будут найдено из хеша)

1) Создать массив всех возможных парных сумм [O(N^2)]

2) Отсортировать этот массив в порядке возрастания [O(N^2 * Log N)]

3) Теперь эта задача сводится к нахождению 2 чисел в отсортированном массиве, которые в сумме дают заданное число X, за линейное время. Используйте 2 указателя: указатель LOW, начиная с самого низкого значения, и указатель HIGH, начиная с самого высокого значения. Если сумма слишком мала, продвигайтесь вперед LOW. Если сумма слишком высока, продвиньте HIGH (назад).В конце концов они найдут эту пару или пересекутся (это легко доказать). Этот процесс занимает линейное время в зависимости от размера массива, то есть O(N ^ 2)

. Это дает общее время O(N^2 * log N) по мере необходимости.

ПРИМЕЧАНИЕ. Этот метод можно обобщить для решения случая M чисел за время O(M * N^(M/2) * log N).

-- РЕДАКТИРОВАТЬ --

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

Я не буду полностью отвечать на ваш вопрос, так как я думаю, что это домашнее задание, а также думаю, что это легко сделать. Но я думаю, что знаю, почему у вас возникли трудности с ответом, поэтому я немного помогу вам.

Во-первых, вы должны изучить рекурсию. Это означает вызов функции из самой себя.

Во-вторых, вы должны использовать вспомогательную функцию, которая вызывается функцией, которую вы хотите написать. Эта функция должна принимать в качестве аргументов: - массив чисел - длина массива - значение, которое вы хотите найти члены, которые в сумме - количество членов массива, которые вы хотите суммировать

Эта функция будет вызываться другой вашей функцией и передавать 4 в качестве последнего аргумента. Затем он вызовет сам себя, корректируя аргументы, пытаясь найти результаты путем частичных проб и ошибок.

edit 2

Поразмыслив, я понял, что это не O(n^2), как я утверждал ранее (я мысленно замазал средние ступени). Он ограничен n ^ 4, но может иметь более низкий предел, чем этот, из-за широких возможностей для сокращения во многих случаях. Однако я не верю, что это сокращение улучшит его до точки n ^ 2.

Злоупотребление тем фактом, что ограничение памяти не указано. И используя обычный подход разделяй и властвуй.

Количество всех перестановок для 4 подмножеств чисел равно C(n,4) и равно O(n^4). Количество всех перестановок для 2 чисел равно C (n, 2) и равно O (n ^ 2). O (n ^ 2), кажется, подходит для этой задачи.

1. Ввод: массив A с n элементами, X.
2. Сгенерируйте все перестановки для 2 числовых подмножеств (это O(n^2)) и поместите их суммы в массив B с n^2 элементами (также запоминая подмножества). Обозначим как S[B[i]] подмножество (состоящее из двух чисел), сумма которых равна B[i].
3. Отсортируйте B, O(n^2*log(n^2)).

4. Проход по массиву B (O(n^2)) i = [0,n^2) и быстрый поиск O(log(n^2) )) = O(log(n)) для значения (X - B[i]). Их может быть несколько (но не более n^2).

   4.1. Пройдитесь по всем элементам со значением (X - B[i]), используя индекс k.

   4.2. Пропустите элементы B[k], где S[B[k]] пересекается с S[B[i]].Пересечение двух наборов с двумя числами можно вычислить за O (1).

   4.3 Если k является индексом элемента, где B[i] + B[k] == X и S[B[k]] не пересекается с S[B[i]], то сумма множеств S[B[k]] и S[B[i]] — четыре искомых числа.

Производительность: O ( n ^ 2 + n ^ 2 * log (n ^ 2) + n ^ 2 * log (n ^ 2)) = O ( n ^ 2 * log (n ^ 2)) = O ( n ^ 2 * log (n) )

На четвертом шаге, когда мы перебираем несколько совпадающих элементов B, используя вложенный цикл. Тем не менее, общее количество итераций двух вложенных циклов ограничено |B|, что равно O(n^2). Быстрый поиск — это не обычный вариант, а тот, который находит соответствующий элемент с наименьшим индексом. (В качестве альтернативы можно использовать обычный bsearch и, поскольку мы могли оказаться в середине, использовать два соседних цикла, проверяя элементы в обоих направлениях.)

Как и несколько других постеров, это можно сделать с помощью хэша за O(n^2)

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <math.h>
#include <map>

using namespace std;

struct Entry
{
   int a;
   int b;
};

int main () {

   typedef vector<int> VI;

   VI l(5);
   l[0] = 1;
   l[1] = 2;
   l[2] = -1;
   l[3] = -2;
   l[4] = 5;
   l[5] = 6;

   sort(l.begin(), l.end());

   int sumTo = 0;

   typedef multimap<int, Entry> Table;

   typedef pair<int,Entry> PairEntry;

   Table myTbl;

   // N
   for (int i = 0; i < l.size(); ++i)
   {
      // N
      for (int j = i+1; j < l.size(); ++j)
      {
         // Const
         int val = l[i] + l[j];

         // A is always less than B
         Entry ent = {i, j};

         myTbl.insert(PairEntry(val,ent));
      }
   }

   pair<Table::iterator, Table::iterator> range;

   // Start at beginning of array
   for (Table::iterator ita = myTbl.begin();
        ita != myTbl.end();
        ++ita)
   {
      int lookFor = sumTo - ita->first;
      // Find the complement
      range = myTbl.equal_range(lookFor);

      // Const bound
      for (Table::iterator itb = range.first;
           itb != range.second;
           ++itb)
      {
         if (ita->second.a == itb->second.a || ita->second.b == itb->second.b)
         {
            // No match
         }
         else
         {
            // Match
            cout << l[ita->second.a] << " " << l[itb->second.a] << " "
                 << l[ita->second.b] << " " << l[itb->second.b] << endl;

            return 0;
         }
      }
   }

   return 0;
}

Звучит как домашнее задание для меня. Но вот что я бы сделал.

Сначала отсортируйте числа (вот ваше n*log(n)).

Теперь создайте указатели на список, инициализируйте его первыми четырьмя числами. Получив это, вы проверяете сумму ваших 4 текущих чисел с общей суммой.Оно должно быть меньше или равно вашей сумме поиска (если это не так, вы можете выйти раньше). Теперь все, что вам нужно сделать, это пройти остальную часть вашего списка, поочередно заменяя ваши указатели текущим значением в списке. Это должно произойти только один раз (или в худшем случае 4 раза), так что есть ваше другое n, что составляет n ^ 2 * log (n)

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