如何求一组N中3个数的总和是否等于M

I want to know how I can implement a better solution than O(N^3). Its similar to the knapsack and subset problems. In my question N<=8000, so i started computing sums of pairs of numbers and stored them in an array. Then I would binary search in the sorted set for each (M-sum[i]) value but the problem arises how will I keep track of the indices which summed up to sum[i]. I know I could declare extra space but my Sums array already has a size of 64 million, and hence I couldn't complete my O(N^2) solution. Please advice if I can do some optimization or if I need some totally different technique.

我想知道我如何实现一个更好的解决方案比O(N ^ 3)。它类似于背包和子集问题。在我的问题N<=8000，所以我开始计算对数字的对，并把它们存储在一个数组中。然后我会在每个(M-sum[I])值的排序集中进行二进搜索，但问题是我如何跟踪求和的指标。我知道我可以声明额外的空间但我总结数组已经有一个大小为6400万,因此我不能完成我的O(N ^ 2)解决方案。如果我能做一些优化，或者我需要一些完全不同的技术，请建议。

6 个解决方案

#1

You could benefit from some generic tricks to improve the performance of your algorithm.

您可以从一些通用的技巧中获益，以改进算法的性能。

1) Don't store what you use only once

1)不要只储存一次你用过的东西

It is a common error to store more than you really need. Whenever your memory requirement seem to blow up the first question to ask yourself is Do I really need to store that stuff ? Here it turns out that you do not (as Steve explained in comments), compute the sum of two numbers (in a triangular fashion to avoid repeating yourself) and then check for the presence of the third one.

存储超过实际需要的内容是一个常见错误。每当你的记忆需要被破坏时，首先要问自己的问题是，我真的需要储存这些东西吗?在这里，你不需要(正如Steve在评论中解释的)计算两个数字的和(以三角形的方式避免重复)，然后检查第三个数字是否存在。

We drop the O(N**2) memory complexity! Now expected memory is O(N).

我们放弃O(N**2)内存复杂性!现在期望的内存是O(N)

2) Know your data structures, and in particular: the hash table

2)了解数据结构，特别是哈希表

Perfect hash tables are rarely (if ever) implemented, but it is (in theory) possible to craft hash tables with O(1) insertion, check and deletion characteristics, and in practice you do approach those complexities (tough it generally comes at the cost of a high constant factor that will make you prefer so-called suboptimal approaches).

完美哈希表很少(如果有的话)实现,但它是(在理论上)可以与O(1)插入工艺哈希表,检查和删除特征,在实践中你接近复杂性(艰难通常发生在高成本的持续的因素,会让你更喜欢所谓的次优方法)。

Therefore, unless you need ordering (for some reason), membership is better tested through a hash table in general.

因此，除非您需要订购(出于某种原因)，否则会员最好通过散列表来进行测试。

We drop the 'log N' term in the speed complexity.

我们在速度复杂度中去掉了log N项。

With those two recommendations you easily get what you were asking for:

有了这两项建议，你很容易得到你想要的:

Build a simple hash table: the number is the key, the index the satellite data associated
构建一个简单的散列表:数字是关键，索引与卫星数据相关。
Iterate in triangle fashion over your data set: for i in [0..N-1]; for j in [i+1..N-1]
在你的数据集上迭代三角法:i in [0..N-1];对j(i + 1 . . n - 1)
At each iteration, check if K = M - set[i] - set[j] is in the hash table, if it is, extract k = table[K] and if k != i and k != j store the triple (i,j,k) in your result.
在每次迭代时，检查K = M - set[i] - set[j]是否在散列表中，如果是，则提取K = table[K]，如果K != i和K !

If a single result is sufficient, you can stop iterating as soon as you get the first result, otherwise you just store all the triples.

如果一个结果是充分的，您可以在得到第一个结果后立即停止迭代，否则您只需存储所有的三元组。

#2

There is a simple O(n^2) solution to this that uses only O(1)* memory if you only want to find the 3 numbers (O(n) memory if you want the indices of the numbers and the set is not already sorted).

有一个简单的O(n ^ 2)解,只使用O(1)*内存如果你只想找到3号(O(n)内存如果你想数字和指标的设置不是已经排序)。

First, sort the set.

首先,一组。

Then for each element in the set, see if there are two (other) numbers that sum to it. This is a common interview question and can be done in O(n) on a sorted set.

然后，对于集合中的每个元素，看看是否有两个(其他的)数字对它求和。这是一个常见的面试问题，可以在O(n)中对排序集进行。

The idea is that you start a pointer at the beginning and one at the end, if your current sum is not the target, if it is greater than the target, decrement the end pointer, else increment the start pointer.

其思想是，你在开始时启动一个指针，在结束时启动一个指针，如果你的当前和不是目标，如果它大于目标，减少末端指针，否则增加开始指针。

So for each of the n numbers we do an O(n) search and we get an O(n^2) algorithm.

所以我们每个n的数字做一个O(n)搜索,我们得到一个O(n ^ 2)算法。

*Note that this requires a sort that uses O(1) memory. Hell, since the sort need only be O(n^2) you could use bubble sort. Heapsort is O(n log n) and uses O(1) memory.

注意，这需要使用O(1)内存的排序。地狱,因为那种只需要O(n ^ 2)你可以用冒泡排序。Heapsort是O(n log n)并使用O(1)内存。

#3

Create a "bitset" of all the numbers which makes it constant time to check if a number is there. That is a start.

为所有的数字创建一个“位集”，这使得检查一个数字是否存在的时间是恒定的。这是一个开始。

The solution will then be at most O(N^2) to make all combinations of 2 numbers.

解决方案将最多O(N ^ 2)让所有两个数字的组合。

The only tricky bit here is when the solution contains a repeat, but it doesn't really matter, you can discard repeats unless it is the same number 3 times because you will hit the "repeat" case when you pair up the 2 identical numbers and see if the unique one is present.

这里唯一棘手的一点是当解决方案包含一个重复,但这并不重要,你可以丢弃重复,除非它是相同数量的3倍,因为你将“重复”情况下当你把两个相同的数字,看看独特的一个是礼物。

The 3 times one is simply a matter of checking if M is divisible by 3 and whether M/3 appears 3 times as you create the bitset.

3 * 1只是检查M是否能被3整除，以及在创建位集时M/3是否出现3次。

This solution does require creating extra storage, up to MAX/8 where MAX is the highest number in your set. You could use a hash table though if this number exceeds a certain point: still O(1) lookup.

这个解决方案确实需要创建额外的存储，最多可以创建MAX/8，其中MAX是集合中最高的数字。

#4

This appears to work for me...

这似乎对我有用……

#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;
}

Okay, here is attempt two: this generates the output:

好的，这是尝试二:它产生输出:

start: 19
size: 4
10005000c
400060008
500050008
600060006

As you can see from there, the first "key" is the three shorts (in hex), 0x0001, 0x0005, 0x000C (which is 1, 5, 12 = 18), etc.

从这里可以看到，第一个“key”是三个short(在十六进制中)、0x0001、0x0005、0x000C(即1,5,12 = 18)等等。

Okay, cleaned up the code some more, realised that the reverse iteration is pointless..

好吧，再清理一下代码，意识到反向迭代毫无意义。

My Big O notation is not the best (never studied computer science), however I think the above is something like, O(N) for outer and O(NlogN) for inner, reason for log N is that std::set::find() is logarithmic - however if you replace this with a hashed set, the inner loop could be as good as O(N) - please someone correct me if this is crap...

我大O符号并不是最好的(从来没有学过计算机科学),然而我认为上面的有点像,O(N)外和O(NlogN)内,O(log N)原因是std::::查找()是对数——但是如果你替换这个散列集内循环可能一样好O(N)-请别人纠正我如果这是废话…

#5

I combined the suggestions by @Matthieu M. and @Chris Hopman, and (after much trial and error) I came up with this algorithm that should be O(n log n + log (n-k)! + k) in time and O(log(n-k)) in space (the stack). That should be O(n log n) overall. It's in Python, but it doesn't use any Python-specific features.

我结合了@Matthieu m和@Chris Hopman的建议，(经过多次尝试和错误)我提出了这个应该是O(n log n + log (n-k)的算法!+ k) in time和O(log(n-k)) in space(栈)总的来说应该是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)

#6

Not trying to boast about my programming skills or add redundant stuff here. Just wanted to provide beginners with an implementation in C++. Implementation based on the pseudocode provided by Charles Ma at Given an array of numbers, find out if 3 of them add up to 0. I hope the comments help.

不要吹嘘我的编程技能，也不要在这里添加多余的东西。只是想为初学者提供c++的实现。根据Charles Ma提供的伪代码在给定数字数组中的实现，找出其中的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;
}

#1