我需要帮助找到一个算法，它可以找到：
- 数组中的四个元素
- 这四个元素的和等于给定的数字X
- 时间复杂度为O(n^2*log(n))
最好提供伪代码或C、C++代码。
在数组中找到四个元素，使它们的和等于给定的数字X。
10
- moti
8
19听起来像是作业。 - Stephen P
3听起来你需要一种方法来找到4个唯一索引的所有排列。 - Martin York
1数字是否大于零？所有数字是否唯一？ - Dummy00001
1X或数字有任何限制吗？ - Nikita Rybak
1你的意思是要编写一个函数，它接受一个数组、它的长度和一个值，并返回一个由数组中4个成员组成的集合，使得它们的总和为该值吗？你希望它返回所有可能的4个成员总和为该值的集合吗？如果没有找到符合条件的集合怎么办？ - nategoose
显示剩余3条评论
11个回答
31
你可以用O(n^2)的时间复杂度来解决。它适用于带有重复和负数的情况。
编辑：正如André在评论中提到的，这个算法使用哈希表来实现时间复杂度，可能会出现最坏情况（虽然比中彩票的概率还要小）。但是你也可以用平衡树（例如Java中的TreeMap）替换哈希表，从而得到稳定的O(n^2*log(n))解决方案。
哈希表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将从哈希表中找到）时，可以找到这个总和。
- Nikita Rybak
11
2如果您使用Tree Map而不是HashTable（在最坏情况下可能具有O(n)的时间复杂度），则可以保证查找总和的时间复杂度为O(log n)。您还应该检查自己是否重复使用了某个数字。 - Andre Holzner
1@Andre 我认为我们不应该考虑哈希表的最坏情况访问时间，这种情况发生的可能性极小 :) 但如果这很重要，那么TreeMap是一个解决方案。 - Nikita Rybak
1@Andre _你还应该检查一下是否有重复使用同一个数字_。这个已经完成了。i和j总是相等的，而且i < j。哈希表包含所有小于i的不同索引k和l的总和。 - Nikita Rybak
2@IVlad 实际上，对于每个特定的总和，我们只需要一对，因此在所有相等的数字的情况下，哈希表将只有一个元素。仍然可能有许多不同的总和具有相同的哈希值，只是难以模拟。 - Nikita Rybak
我不明白你如何确保不重复使用一个数字？我看了你回复安德烈的评论，但仍然不清楚。能否请您详细说明一下？ - Hengameh
显示剩余6条评论
4
像其他几位帖子作者一样，可以使用哈希表在 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;
}
- Sibshops
2
1这符合要求，所以加1分，但它并不像你说的那样是O(n^2)。C++ multimap不能提供常数时间的插入和查找，它们是对数时间。 - IVlad
@IVlad 但我认为将其更改为“unordered_multimap”将解决问题。 - user9989615
4
滥用未指定内存限制的事实。并使用通常的分而治之方法。
4个数字子集的所有排列数为C(n,4)，为O(n^4)。2个数字的所有排列数为C(n,2)，为O(n^2)。 O(n^2)似乎对这个任务来说是可以接受的。
4个数字子集的所有排列数为C(n,4)，为O(n^4)。2个数字的所有排列数为C(n,2)，为O(n^2)。 O(n^2)似乎对这个任务来说是可以接受的。
- 输入是一个由n个元素组成的数组A和X。
- 生成所有2个数字子集的排列(复杂度为O(n^2))，并将它们的和放入由n^2个元素组成的数组B中(同时记住这些子集)。我们用S[B[i]]表示和为B[i]的子集(由两个数字组成)。
- 对B进行排序，复杂度为O(n^2*log(n^2))。
遍历数组B(O(n^2))，对于值为(X-B[i])的元素进行快速搜索(O(log(n^2)) = O(log(n)))。可能有多个这样的元素(但不超过n^2个)。
4.1 遍历所有值为(X-B[i])的元素，使用索引k。
4.2 跳过S[B[k]]与S[B[i]]相交的元素B[k]。两个由两个数字组成的集合的交集可以在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，因为我们可能已经落在了中间，所以要使用两个相邻的循环，在两个方向上检查元素。）
- Dummy00001
4
4
log(n^2)等于2log(n)，所以时间复杂度不会超过。但是这并没有考虑重复元素的情况，需要进行额外的检查来解决。例如给定数组 [1, 2, 3] 和所有和的组合 [ 1+2, 1+3, 2+3 ]，可以用 4 + 5 得到期望的和 9，但是其中的 3 被重复计算了。 - Anurag1@Anurag：天啊，我得重复做这道数学题。 - Dummy00001
您能详细说明第四步吗？您如何处理重复项和过度/欠计数的情况？ - IVlad
你如何检查它们是否有交集？（例如，你如何检查S[B[k]]与S[B[i]]不相交？） - Hengameh
2
Nikita Rybak提供的算法的一个可行的Java解决方案...
// find four numbers in an array such that they equals to X
class Pair{
int i;
int j;
Pair(int x,int y){
i=x;
j=y;
}
}
public class FindNumbersEqualsSum {
public static void main(String[] args) {
int num[]={1,2,3,4,12,43,32,53,8,-10,4};
get4Numbers(num, 17);
get4Numbers(num, 55);
}
public static void get4Numbers(int a[],int sum){
int len=a.length;
Map<Integer, Pair> sums = new HashMap<Integer, Pair>();
for (int i = 0; i < len; ++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 < len; ++j) {
int current = a[i] + a[j];
int rest = sum - 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.containsKey(rest)) {
// found it
Pair p = sums.get(rest);
System.out.println(a[i]+" + "+a[j]+" + "+a[p.i] +" + "+a[p.j]+" = "+sum);
}
}
// 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.put(a[i] + a[k],new Pair(i, k));
}
}
}
}
Result:
4 + 8 + 3 + 2 = 17
8 + 4 + 4 + 1 = 17
43 + 8 + 3 + 1 = 55
32 + 8 + 12 + 3 = 55
8 + -10 + 53 + 4 = 55
-10 + 4 + 8 + 53 = 55
- Explorer
3
这实际上并没有处理重复项 - - pyrometer
显示 53 + 8 + 4 + 3 = 68 和 8 + 4 + 53 + 3 = 68 - pyrometer
请问一下，“class pair”是什么意思，为什么在这里使用它？ - Hengameh
1
1) 创建一个包含所有可能的数对和的数组 [O(N^2)]
2) 将此数组按升序排序 [O(N^2 * Log N)]
3) 现在，这个问题可以简化为在线性时间内找到一个已排序数组中两个数的和等于给定数字X。使用两个指针：一个从最小值开始的LOW指针，一个从最大值开始的HIGH指针。如果总和太低，则将LOW指针向前移动。如果总和太高，则将HIGH指针向后移动。最终它们将找到那一对或相互交叉（这很容易证明）。这个过程需要线性时间，即O(N ^ 2)
这样就得到了所需的O(N^2 * log N)的总时间。
注意：这种方法可以推广到解决M个数字的情况，时间复杂度为O(M * N^(M/2) * log N)。
-- 编辑 --
实际上，我的回答与Dummy00001的回答非常相似，只是最后的查找方法不同（尽管总体复杂度相同...）
- Eyal Schneider
5
+1 不错的解决方案。但是这里有一个问题：假设您正在搜索
sum=18。并且 a = {2,3,4,5,7,9,10} 现在 a[0]+a[1]=5 和 a[2]+a[5]=13，因此 a[0]+a[1]+a[2]+a[5]=18。但是 a[1]+a[2]=7 和 a[0]+a[5]=11 因此 a[0]+a[1]+a[2]+a[5]=18。因此，您的解决方案将打印这两个而不是1。那么您将如何解决这个问题。谢谢。 - Trying1@Trying: 算法不需要打印特定的四个数字；任何满足要求和的四个不同数字都可以。我的解决方案问题在于独特性。它可能会将一个数组数字包含两次。这可以通过将成对数字存储在映射中，并仅在它们没有共同值时接受两个成对之间的匹配来解决。 - Eyal Schneider
真的。感谢您的确认。今天我在调试您的解决方案时发现了这个问题，因此想向作者确认一下。谢谢。 - Trying
你如何判断“两对没有共同的价值”？ - Hengameh
1@Hengameh：对于sums数组中的每个和，您还可以存储原始数组中2个值的索引。在第3步中，为避免找到错误的组合，请验证LOW的2个索引与HIGH的2个索引没有共同的值。如果LOW有K个重复值，HIGH有L个重复值，并且所有组合都产生正确的和X，则只需检查所有组合即可。运行此交叉检查一次或多次的开销最多为O（N ^ 2），因此不会改变总体复杂度。 - Eyal Schneider
0
我编写了一个O(N^^2)的运行时间函数，它不使用哈希表，但可以处理负数和重复数字。我通过在整数数组中添加一个大正数（例如100）来处理负数，然后将目标调整为target += (4 * 100)。当我找到结果时，我从结果中减去100。以下是我的代码和测试用例，请告诉我这是否具有O(N^^2)的时间复杂度。
struct maryclaranicholascameron{
int sum;
int component1;
int component2;
};
void Another2PrintSum(int arr[], int arraysize, int target){
int i(arraysize -1);
int j(arraysize -2);
int temp(target);
int temp2(0);
int m(0);
int n(0);
int sum(0);
int original_target(target);
for (int ctr = 0; ctr < arraysize; ctr++){
sum += arr[ctr];
}
for (int ctrn = 0; ctrn < arraysize; ctrn++){
arr[ctrn] += 100;
}
maryclaranicholascameron* temparray = new maryclaranicholascameron[sum + (arraysize *100)];
memset(temparray, 0, sizeof(maryclaranicholascameron) * (sum + 400));
for (m = 0; m < arraysize; m++){
for (n = m + 1; n < arraysize; n++){
temparray[arr[m] + arr[n]].sum = arr[m]+ arr[n];
temparray[arr[m] + arr[n]].component1 = m;
temparray[arr[m] + arr[n]].component2 = n;
}
}
target += (4 * 100);
original_target = target;
bool found(false);
while (i >= 0 && i < arraysize && found == false){
target -= (arr[i]);
while(j >= 0 && j < arraysize && found == false){
temp2 = target;
target -= (arr[j]);
if (i != j && temparray[target].sum == target &&
temparray[target].sum != 0 &&
temparray[target].component1 != i &&
temparray[target].component2 != i &&
temparray[target].component1 != j &&
temparray[target].component2 != j){
printf("found the 4 integers i = %d j = %d m = %d n = %d component1 = %d component = %d i %d j %d\n",
arr[i] - 100,
arr[j] - 100,
arr[temparray[target].component1] - 100,
arr[temparray[target].component2] - 100,
temparray[target].component1,
temparray[target].component2,
i,
j);
found = true;
break;
}
j -= 1;
target = temp2;
}
i -= 1;
j = i;
target = original_target;
}
if (found == false){
printf("cannot found the 4 integers\n");
}
delete [] temparray;
}
// test cases
int maryclaranicholas[] = {-14,-14,-14,-14,-12 ,-12, -12 ,-12 ,-11, -9,-8,-7,40};
Another2PrintSum(maryclaranicholas, 13,-2};
int testarray[] = {1,3,4,5,7,10};
Another2PrintSum(testarray, 6, 20);
- Frank
1
抱歉，我并不是在批评这篇文章，但我认为有很多可以改进的地方。首先，尝试以更有意义的方式命名变量，这样它将更易于阅读。其次，你的
temparray 只存储了1对索引，这些索引加起来等于特定的目标。如果在迭代过程中发现这一对会与最终循环中的另一对相交，但还有另一对不会怎么办？这基本上就是为什么"Sibshops"的答案使用了multi-map。 - user99896150
这个问题可以看作是帕斯卡恒等式的一个变化，
以下是完整的代码：
请原谅，代码是用Java编写的：
以下是完整的代码：
请原谅，代码是用Java编写的：
public class Combination {
static int count=0;
public static void main(String[] args) {
int a[] = {10, 20, 30, 40, 1, 2,4,11,60,15,5,6};
int setValue = 4;
getCombination(a, setValue);
}
private static void getCombination(int[] a, int setValue) {
// TODO Auto-generated method stub
int size = a.length;
int data[] = new int[setValue];
createCombination(a, data, setValue, 0, 0, size);
System.out.println(" total combinations : "+count);
}
private static void createCombination(int[] a, int[] data, int setValue,
int i, int index, int size) {
// TODO Auto-generated method stub
if (index == setValue) {
if(data[0]+data[1]+data[3]+data[2]==91)
{ count ++;
for (int j = 0; j < setValue; j++)
System.out.print(data[j] + " ");
System.out.println();
}return;
}
// System.out.println(". "+i);
if (i >= size)
return;
// to take care of repetation
if (i < size - 2) {
while (a[i] == a[i + 1])
i++;
}
data[index] = a[i];
// System.out.println(data[index]+" "+index+" .....");
createCombination(a, data, setValue, i + 1, index + 1, size);
createCombination(a, data, setValue, i + 1, index, size);
}
}
示例输入：
int a[] = {10, 20, 30, 40, 1, 2,4,11,60,15,5,6};
输出：：
10 20 1 60
10 30 40 11
10 60 15 6
20 30 40 1
20 60 5 6
30 40 15 6
11 60 15 5
total combinations : 7
- sourav palmal
1
这种方法的时间复杂度是多少？ - Hengameh
0
这个问题可以简化为找到所有长度为4的组合。对于每个得到的组合，求和元素并检查它是否等于X。
- Deepthi
1
这个解决方案的时间复杂度是多少？你能提供一下代码吗？ - Hengameh
0
听起来像是一道作业题。但这是我会做的。
首先对数字进行排序（这就是n*log(n)）。
现在，创建指向列表的指针，并用前4个数字初始化它。一旦完成，您可以检查当前4个数字的总和与目标总和是否小于或等于。如果不是，您可以提前退出。现在，您只需要遍历列表的其余部分，交替地将指针替换为列表中的当前值。这只需要发生一次（或者最坏情况下4次），所以这就是另一个n，使得n^2*log(n)。
您需要跟踪一些逻辑，以了解您是否超过/低于您的总和以及下一步该怎么做，但我把它留给您作为家庭作业。
- miked
4
6遍历列表的其余部分，交替将指针替换为列表中的当前值。 - Nikita Rybak
1你能详细说明如何使用四个指针遍历列表吗？你是让第一个指针先到达末尾，然后再移动第二个指针等吗？ - Andre Holzner
1顺便说一下，这将是O(n) + O(n * log(n)) = O(n * log(n))，而不是O(n) * O(n * log(n))。 - Andre Holzner
所以，你的意思是可以用O(nlogn)完成吗？ - Hengameh
0
我不会完全回答你的问题，因为我认为这是一道作业题，而且我认为这很容易做到。但我确实知道你为什么难以得到答案，所以我会帮你一点忙。
首先，你应该研究递归。也就是说，从函数内部调用自身。
其次，你应该使用一个辅助函数，由你想要编写的函数调用。这个函数应该接受以下参数： - 一个数字数组 - 数组的长度 - 你想要找到总和为多少的成员的值 - 你想要求和的数组成员数量
这个函数将被你的其他函数调用，并传递一个4作为最后一个参数。然后它将调用自身，调整参数，尝试通过部分试错来找到结果。
编辑2
经过进一步思考，我意识到这不是O(n^2)，正如我之前声称的那样（我在中间步骤上粗略地忽略了）。它受到n^4的限制，但由于在许多情况下有充足的机会进行简化，可能会有比这更低的限制。但我不认为这种简化能够将其提高到n^2的水平。
- nategoose
4
那么你如何证明其复杂度符合要求呢？ - Maciej Hehl
1所以你认为这很容易做到，然后最终意识到自己不知道如何做。很好，-1。 - IVlad
@IVLad：我本可以删除这个答案，避免被踩，但我选择保留它，并指出其中的缺陷。 - nategoose
谢谢大家，今天经过几个小时的努力，我得出了与你们类似的答案。
我不需要所有可能的4个数字，我只需要一个选项。
我的解决方案也具有O(n^2)的空间复杂度。 - moti
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接