找到数组中的四个元素,其总和等于给定的数字X

我需要帮助才能找到一个找到的算法:

  • 数组中的四个元素
  • 其总和等于给定数字X.
  • 在O(n ^ 2 * log(n))

喜欢伪代码或c,c ++

你可以在O(n ^ 2)中完成。 与重复和负数一起工作正常。

编辑安德烈在评论中指出,时间是使用哈希,这是“最坏情况”(虽然它比在彩票中获胜的可能性小)。 但是你也可以用平衡树(java中的TreeMap)替换hashtable并获得保证稳定的O(n ^ 2 * log(n))解决方案。

Hashtable sums将存储两个不同元素的所有可能总和。 对于每个和S它返回一对索引ij ,使得a[i] + a[j] == Si != 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 = 7j = 10并且rest = a[1] + a[3]时将找到此总和(将从散列中找到索引1和3)

像其他一些海报一样,它可以用O(n ^ 2)中的散列来完成

 #include  #include  #include  #include  #include  #include  using namespace std; struct Entry { int a; int b; }; int main () { typedef vector 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 Table; typedef pair 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 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; } 

滥用没有指定内存约束的事实。 并使用通常的分而治之的方法。

4个数字子集的所有排列的数量是C(n,4)并且是O(n ^ 4)。 2个数的所有排列的数量是C(n,2)并且是O(n ^ 2)。 O(n ^ 2)似乎可以完成任务。

  1. 输入是:具有n元素X的数组A
  2. 为2个数字子集(即O(n ^ 2))生成所有排列,并将它们的总和放入具有n ^ 2个元素的数组B (也记住子集)。 设S[B[i]]表示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。 使用索引k遍历所有具有(X - B[i])值的元素。

    4.2。 跳过元素B[k] ,其中S[B[k]]S[B[i]]相交。 可以在O(1)中计算具有两个数字的两组的交集。

    4.3如果k是索引,其中B[i] + B[k] == XS[B[k]]不与S[B[i]]相交的元素,那么集合S[B[k]]的总和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 ,因为我们可能在中间着陆,使用两个相邻的循环,检查两个方向上的元素。)

算法的Java解决方案。 由Nikita Rybak提供..

 // 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 sums = new HashMap(); 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[pi] +" + "+a[pj]+" = "+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 

1)创建所有可能的对和的数组[O(N ^ 2)]

2)按升序排序此数组[O(N ^ 2 * Log N)]

3)现在,这个问题减少到在线性时间内在排序数组中找到总和为给定数X的2个数字。 使用2个指针:从最低值开始的LOW指针和从最高值开始的HIGH指针。 如果总和太低,则提前LOW。 如果总和太高,则提前HIGH(向后)。 最终他们会找到那对或相互交叉(这很容易certificate)。 此过程需要数组大小的线性时间,即O(N ^ 2)

这根据需要给出总时间O(N ^ 2 * log N)。

注意 :该方法可以推广用于求解O(M * N ^(M / 2)* log N)时间内M个数的情况。

– 编辑 –

实际上我的回答与Dummy00001的响应非常相似,除了最终查找,我使用更快的方法(尽管整体复杂性相同……)

听起来像是家庭作业。 但这就是我要做的。

首先对数字进行排序(这是你的n * log(n))。

现在,创建指向列表的指针,使用前4个数字初始化它。 完成后,检查4个当前数字与总数的总和。 它应小于或等于您的搜索总和(如果不是,您可以提前退出)。 现在您需要做的就是遍历列表的其余部分,交替使用列表中的当前值替换指针。 这只需要发生一次(或者实际上最坏的情况下发生4次),所以你的另外一个n,这使得n ^ 2 * log(n)

您需要跟踪一些逻辑,以了解您是否超过/低于您的总和以及下一步该做什么,但我将其作为您的家庭作业。

我不会完全回答你的问题,因为我认为这是家庭作业,并且认为这很容易做到。 但我确实认为我知道你为什么难以回答,所以我会帮助你一点点。

首先,你应该考虑递归。 这意味着从内部调用函数。

其次,您应该使用辅助函数,该函数由您要编写的函数调用。 这个函数应该作为参数: – 一个数字数组 – 数组的长度 – 你想要找到总和的成员的值 – 你要总结的数组成员的数量

此函数将由您的其他函数调用,并为最后一个参数传递4。 然后它会调用自己调整参数,因为它试图通过部分尝试和错误来查找结果。

编辑2

经过进一步的思考,我意识到这不是O(n ^ 2),正如我之前所声称的那样(我精神上掩饰了中间步骤)。 它受到n ^ 4的限制,但可能有一个下限,因为在很多情况下有充分的捷径机会。 不过,我不认为这种短切将其提高到n ^ 2的程度。

在数组中找到四个元素,其总和等于给定的数字X.
对我来说跟随算法工作:

 Dim Amt(1 To 10) As Long Dim i For i = 1 To 10 Amt(i) = Val(List1.List(i)) Next i Dim Tot As Integer Dim lenth As Integer lenth = List1.ListCount 'sum of 4 numbers For i = 1 To lenth For j = 1 To lenth For k = 1 To lenth For l = 1 To lenth If i <> j And i <> k And i <> l And j <> k And j <> l And k <> l Then Debug.Print CBAmt(i) & " , " & CBAmt(j) & " , " & CBAmt(k) & " , " & CBAmt(l) If CBAmt(i) + CBAmt(j) + CBAmt(k) + CBAmt(l) = Val(Text1) Then MsgBox "Found" found = True Exit For End If End If Next If found = True Then Exit For Next If found = True Then Exit For Next If found = True Then Exit For Next 

我写了一个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 = %dj = %dm = %dn = %d component1 = %d component = %di %dj %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); 

这个问题可以减少到找到长度为4的所有组合。对于这样获得的每个组合,对元素求和并检查它是否等于X.

这个问题可以作为帕斯卡身份的变体,

这是完整的代码:

请原谅代码在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