Как найти, если 3 числа в наборе размера N точно суммируют до M

Question

Я хочу знать, как я могу реализовать лучшее решение, чем O (N ^ 3). Это похоже на проблемы с рюкзаком и подмножеством. В моем вопросе N <= 8000, поэтому я начал вычислять суммы пар чисел и сохранил их в массиве. Затем я выполняю двоичный поиск в отсортированном наборе для каждого значения (M-sum [i]), но возникает проблема, как я буду отслеживать индексы, которые суммируются до суммы [i]. Я знаю, что могу объявить дополнительное пространство, но мой массив Sums уже имеет размер 64 миллиона, и, следовательно, я не смог завершить свое решение O (N ^ 2). Пожалуйста, посоветуйте, если я могу провести некоторую оптимизацию или мне нужна совершенно другая техника. </p>

Answer 1

Вы можете воспользоваться некоторыми общими приемами для повышения производительности вашего алгоритма.

1) Не храните то, что вы используете, только один раз

Распространенная ошибка - хранить больше, чем вам действительно нужно. Всякий раз, когда кажется, что ваши требования к памяти взрывают, первый вопрос, который вы задаете себе: Действительно ли мне нужно хранить эти вещи? Здесь оказывается, что вы не (как объяснил Стив в комментариях) вычислить сумму два числа (треугольным способом, чтобы избежать повторения), а затем проверьте наличие третьего.

Мы отбрасываем O (N ** 2) сложность памяти! Теперь ожидаемая память O (N).

2) Знайте свои структуры данных, и в частности: хеш-таблицу

Идеально Хеш-таблицы используются редко (если вообще когда-либо), но (теоретически) возможно создать хеш-таблицы с O (1) характеристиками вставки, проверки и удаления, и на практике вы подходите эти сложности (хотя обычно это происходит за счет высокого постоянного фактора, который заставит вас предпочесть так называемые неоптимальные подходы).

Поэтому, если вам не нужен порядок (по какой-то причине), членство лучше проверять с помощью хеш-таблицы в целом.

Мы отбрасываем термин 'log N' в сложности скорости.

С этими двумя рекомендациями вы легко получите то, что просили:

1. Создайте простую хеш-таблицу: номер является ключом, индекс, связанный со спутниковыми данными
2. Выполните итерацию в виде треугольника для вашего набора данных: for i in [0..N-1]; for j in [i+1..N-1]
3. На каждой итерации проверяйте, есть ли K = M - set[i] - set[j] в хеш-таблице, если это так, извлекайте k = table[K] и , если k != i и k != j сохраняют тройной (i,j,k) в вашем результате .

Если одного результата достаточно, вы можете прекратить итерации, как только получите первый результат, в противном случае вы просто сохраните все тройки.

Answer 2

Существует простое решение O (n ^ 2), которое использует только память O (1) *, если вы хотите найти только память из 3 чисел (O (n), если вы хотите, чтобы индексы чисел инабор еще не отсортирован).

Сначала отсортируйте набор.

Затем для каждого элемента в наборе посмотрите, есть ли два (другие) числа, которые суммируют его.Это распространенный вопрос интервью, и его можно задать в O (n) для отсортированного набора.

Идея состоит в том, что вы начинаете указатель с начала и с одного в конце, если текущая сумма нецель, если она больше цели, уменьшать указатель конца, иначе увеличивать указатель начала.

Таким образом, для каждого из n чисел мы выполняем поиск O (n) и получаем O (n ^2) алгоритм.

---

* Обратите внимание, что для этого требуется сортировка, использующая O (1) памяти.Черт, так как сортировка должна быть только O (n ^ 2), вы можете использовать пузырьковую сортировку.Heapsort - это O (n log n) и использует O (1) памяти.

Answer 3

Создайте «битовый набор» всех чисел, что делает постоянным время проверки наличия номера.Это начало.

Тогда решение будет не более O (N ^ 2), чтобы сделать все комбинации из 2 чисел.

Единственный сложный момент здесь, когда решение содержит повтор, но это на самом деле не имеет значения, вы можете сбросить повторы, если это не одно и то же число 3 раза, потому что вы попадете в случай «повторения», когда вы объедините два одинаковых числа и посмотрите, присутствует ли уникальное число.

3 раза просто проверить, делится ли M на 3 и появляется ли M / 3 3 раза при создании набора битов.

Это решение требует создания дополнительного хранилища, вплоть до MAX/ 8 где MAX - наибольшее число в вашем наборе.Вы можете использовать хеш-таблицу, хотя, если это число превышает определенную точку: по-прежнему O (1) поиск.

Answer 4

Не пытайтесь хвастаться своими навыками программирования или добавлять лишние вещи здесь.Просто хотел предоставить начинающим реализацию в C ++.Реализация основана на псевдокоде, предоставленном Чарльзом Ма в . Учитывая массив чисел, выясните, составляют ли 3 из них 0 .Я надеюсь, что комментарии помогут.

#include <iostream>
using namespace std;

void merge(int originalArray[], int low, int high, int sizeOfOriginalArray){
    //    Step 4: Merge sorted halves into an auxiliary array
    int aux[sizeOfOriginalArray];
    int auxArrayIndex, left, right, mid;

    auxArrayIndex = low;
    mid = (low + high)/2;
    right = mid + 1;
    left = low;

    //    choose the smaller of the two values "pointed to" by left, right
    //    copy that value into auxArray[auxArrayIndex]
    //    increment either left or right as appropriate
    //    increment auxArrayIndex
    while ((left <= mid) && (right <= high)) {
        if (originalArray[left] <= originalArray[right]) {
            aux[auxArrayIndex] = originalArray[left];
            left++;
            auxArrayIndex++;
        }else{
            aux[auxArrayIndex] = originalArray[right];
            right++;
            auxArrayIndex++;
        }
    }

    //    here when one of the two sorted halves has "run out" of values, but
    //    there are still some in the other half; copy all the remaining values
    //    to auxArray
    //    Note: only 1 of the next 2 loops will actually execute
    while (left <= mid) {
        aux[auxArrayIndex] = originalArray[left];
        left++;
        auxArrayIndex++;
    }

    while (right <= high) {
        aux[auxArrayIndex] = originalArray[right];
        right++;
        auxArrayIndex++;
    }

    //    all values are in auxArray; copy them back into originalArray
    int index = low;
    while (index <= high) {
        originalArray[index] = aux[index];
        index++;
    }
}

void mergeSortArray(int originalArray[], int low, int high){
    int sizeOfOriginalArray = high + 1;
    //    base case
    if (low >= high) {
        return;
    }

    //    Step 1: Find the middle of the array (conceptually, divide it in half)
    int mid = (low + high)/2;

    //    Steps 2 and 3: Recursively sort the 2 halves of origianlArray and then merge those
    mergeSortArray(originalArray, low, mid);
    mergeSortArray(originalArray, mid + 1, high);
    merge(originalArray, low, high, sizeOfOriginalArray);
}

//O(n^2) solution without hash tables
//Basically using a sorted array, for each number in an array, you use two pointers, one starting from the number and one starting from the end of the array, check if the sum of the three elements pointed to by the pointers (and the current number) is >, < or == to the targetSum, and advance the pointers accordingly or return true if the targetSum is found.

bool is3SumPossible(int originalArray[], int targetSum, int sizeOfOriginalArray){
    int high = sizeOfOriginalArray - 1;
    mergeSortArray(originalArray, 0, high);

    int temp;

    for (int k = 0; k < sizeOfOriginalArray; k++) {
        for (int i = k, j = sizeOfOriginalArray-1; i <= j; ) {
            temp = originalArray[k] + originalArray[i] + originalArray[j];
            if (temp == targetSum) {
                return true;
            }else if (temp < targetSum){
                i++;
            }else if (temp > targetSum){
                j--;
            }
        }
    }
    return false;
}

int main()
{
    int arr[] = {2, -5, 10, 9, 8, 7, 3};
    int size = sizeof(arr)/sizeof(int);
    int targetSum = 5;

    //3Sum possible?
    bool ans = is3SumPossible(arr, targetSum, size); //size of the array passed as a function parameter because the array itself is passed as a pointer. Hence, it is cummbersome to calculate the size of the array inside is3SumPossible()

    if (ans) {
        cout<<"Possible";
    }else{
        cout<<"Not possible";
    }

    return 0;
}

Answer 5

Я объединил предложения @Matthieu M. и @Chris Hopman, и (после долгих проб и ошибок) я придумал этот алгоритм, который должен быть O (n log n + log (nk)! + K) во времени и O (log (nk)) в пространстве (стек). Это должно быть O (n log n) в целом. Он написан на Python, но не использует никаких специфических для Python функций.

import bisect

def binsearch(r, q, i, j): # O(log (j-i))
    return bisect.bisect_left(q, r, i, j)

def binfind(q, m, i, j):    
    while i + 1 < j:
        r = m - (q[i] + q[j])
        if r < q[i]:
            j -= 1
        elif r > q[j]:
            i += 1
        else:
            k = binsearch(r, q, i + 1, j - 1)  # O(log (j-i))
            if not (i < k < j):
                return None
            elif q[k] == r:
                return (i, k, j)
            else:
                return (
                    binfind(q, m, i + 1, j)
                    or
                    binfind(q, m, i, j - 1)
                    )

def find_sumof3(q, m):
    return binfind(sorted(q), m, 0, len(q) - 1)

Answer 6

Мне кажется, это работает ...

#include <iostream>
#include <set>
#include <algorithm> 
using namespace std;

int main(void)
{
  set<long long> keys;

  // By default this set is sorted
  set<short> N;
  N.insert(4);
  N.insert(8);
  N.insert(19);
  N.insert(5);
  N.insert(12);
  N.insert(35);
  N.insert(6);
  N.insert(1);

  typedef set<short>::iterator iterator;

  const short M = 18;

  for(iterator i(N.begin()); i != N.end() && *i < M; ++i)
  {
    short d1 = M - *i; // subtract the value at this location
    // if there is more to "consume"
    if (d1 > 0)
    {
      // ignore below i as we will have already scanned it...
      for(iterator j(i); j != N.end() && *j < M; ++j)
      {
        short d2 = d1 - *j; // again "consume" as much as we can
        // now the remainder must eixst in our set N
        if (N.find(d2) != N.end())
        {
          // means that the three numbers we've found, *i (from first loop), *j (from second loop) and d2 exist in our set of N
          // now to generate the unique combination, we need to generate some form of key for our keys set
          // here we take advantage of the fact that all the numbers fit into a short, we can construct such a key with a long long (8 bytes)

          // the 8 byte key is made up of 2 bytes for i, 2 bytes for j and 2 bytes for d2
          // and is formed in sorted order

          long long key = *i; // first index is easy
          // second index slightly trickier, if it's less than j, then this short must be "after" i
          if (*i < *j)
            key = (key << 16) | *j; 
          else
            key |= (static_cast<int>(*j) << 16); // else it's before i

          // now the key is either: i | j, or j | i (where i & j are two bytes each, and the key is currently 4 bytes)

          // third index is a bugger, we have to scan the key in two byte chunks to insert our third short
          if ((key & 0xFFFF) < d2)
            key = (key << 16) | d2;  // simple, it's the largest of the three
          else if (((key >> 16) & 0xFFFF) < d2)
            key = (((key << 16) | (key & 0xFFFF)) & 0xFFFF0000FFFFLL) | (d2 << 16); // its less than j but greater i
          else
            key |= (static_cast<long long>(d2) << 32); // it's less than i

          // Now if this unique key already exists in the hash, this won't insert an entry for it
          keys.insert(key);
        }
        // else don't care...
      }
    }
  }
  // tells us how many unique combinations there are  
  cout << "size: " << keys.size() << endl;
  // prints out the 6 bytes for representing the three numbers
  for(set<long long>::iterator it (keys.begin()), end(keys.end()); it != end; ++it)
     cout << hex << *it << endl;

  return 0;
}

Хорошо, вот вторая попытка: генерируется вывод:

start: 19
size: 4
10005000c
400060008
500050008
600060006

Как вы можете видеть,первый «ключ» - это три шорта (в шестнадцатеричном виде), 0x0001, 0x0005, 0x000C (что составляет 1, 5, 12 = 18) и т. д.обратная итерация бессмысленна.

Моя запись Big O не самая лучшая (никогда не изучала информатику), однако я думаю, что выше приведено что-то вроде: O(N) для внешнего и O(NlogN) для внутреннего, причинаlog N в том, что std::set::find() является логарифмическим - однако, если вы замените его хэшированным набором, внутренний цикл может быть таким же, как O(N) - пожалуйста, кто-то поправит меня, если это дерьмо ...