如何找到一组大小N中的3个数字是否恰好总计为M. [英] How to find if 3 numbers in a set of size N exactly sum up to M

问题描述

我想知道如何实现比O（N ^ 3）更好的解决方案。它类似于背包和子集问题。在我的问题N <= 8000，所以我开始计算数对的和，并将它们存储在一个数组。然后我将对每个（M-sum [i]）值的排序集中进行二分搜索，但是问题出现我如何跟踪总和到sum [i]的索引。我知道我可以声明额外的空间，但我的Sums数组已经有6400万的大小，因此我不能完成我的O（N ^ 2）解决方案。

解决方案

你可以从一些通用的技巧中受益提高你的算法的性能。

1）不要存储你只使用一次

一个常见的错误存储多于你真正需要的。每当你的内存需求似乎爆炸了第一个问题，问自己是我真的需要存储这些东西吗？这里结果是，你不（如史蒂夫在评论中解释的），计算sum

我们删除了第一个数字的O （N ** 2）内存复杂度！现在预期的内存是O（N）。

2）知道你的数据结构，

完美哈希表很少实现，但是（理论上）可以用O（1）插入，检查和删除特征，在实践中，你会接近这些复杂性（通常是以高常数因素为代价，这将使你更喜欢所谓的<次优次方法）。

因此，除非你需要排序（由于某种原因），一般来说通过哈希表测试成员资格。

我们在速度复杂度中删除log N项。

有了这两个建议， for：

1. 建立一个简单的哈希表：数字是键，卫星数据的索引


2. 以三角形迭代您的数据集： for i in [0..N-1];对于j在[i + 1..N-1]


3. 在每次迭代时，检查 K = M - set [i ] - set [j] 在散列表中，如果是，则提取 k = table [K] c $ c> k！= i 和 k！= j 。

如果单个结果已足够，您可以尽快停止迭代当你得到第一个结果，否则你只存储所有三元组。

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.

解决方案

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

1) Don't store what you use only once

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.

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

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

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).

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.

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

1. Build a simple hash table: the number is the key, the index the satellite data associated
2. Iterate in triangle fashion over your data set: for i in [0..N-1]; for j in [i+1..N-1]
3. 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.

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.

这篇关于如何找到一组大小N中的3个数字是否恰好总计为M.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！