# 找到四个总和为给定值的元素| 系列 2 > 原文： [https://www.geeksforgeeks.org/find-four-elements-that-sum-to-a-given-value-set-2/](https://www.geeksforgeeks.org/find-four-elements-that-sum-to-a-given-value-set-2/) 给定一个整数数组，请找到该数组中四个元素的总和等于给定值 X 的任意组合。 **例如** ``` Input: array = {10, 2, 3, 4, 5, 9, 7, 8} X = 23 Output: 3 5 7 8 Sum of output is equal to 23, i.e. 3 + 5 + 7 + 8 = 23. Input: array = {1, 2, 3, 4, 5, 9, 7, 8} X = 16 Output: 1 3 5 7 Sum of output is equal to 16, i.e. 1 + 3 + 5 + 7 = 16. ``` 在此主题的先前文章中，我们在[中讨论了 **O（n ^ 3）**算法。 借助辅助空间，可以在 **O（n ^ 2Logn）**时间内解决该问题。](https://www.geeksforgeeks.org/find-four-numbers-with-sum-equal-to-given-sum/) *感谢它的建议方法。 以下是详细的过程。* **方法 1**： 两个指针算法。 **方法**：令输入数组为 A []。 1. 创建一个辅助数组 aux []并将所有可能的对的和存储在 aux []中。 aux []的大小将为 n *（n-1）/ 2，其中 n 是 A []的大小。 2. 排序辅助数组 aux []。 3. 现在问题减少了，在 aux []中找到两个元素，它们的总和等于 X。我们可以使用本文的方法 1 来高效地找到两个元素。 但是，需要注意以下重要点： aux []的元素表示来自 A []的一对。 在从 aux []中选择两个元素时，我们必须检查两个元素是否具有共同的 A []元素。 例如，如果第一个元素的总和为 A [1]和 A [2]，第二个元素的总和为 A [2]和 A [4]，则 aux []的这两个元素不代表四个元素 输入数组 A []。 下面是上述方法的实现： ## C++ ```cpp #include <bits/stdc++.h> using namespace std; // The following structure is needed // to store pair sums in aux[] class pairSum { public:     // index (int A[]) of first element in pair     int first;     // index of second element in pair     int sec;     // sum of the pair     int sum; }; // Following function is needed // for library function qsort() int compare(const void* a, const void* b) {     return (         (*(pairSum*)a).sum         - (*(pairSum*)b).sum); } // Function to check if two given pairs // have any common element or not bool noCommon(pairSum a, pairSum b) {     if (a.first == b.first         || a.first == b.sec         || a.sec == b.first         || a.sec == b.sec)         return false;     return true; } // The function finds four // elements with given sum X void findFourElements(     int arr[], int n, int X) {     int i, j;     // Create an auxiliary array     // to store all pair sums     int size = (n * (n - 1)) / 2;     pairSum aux[size];     /* Generate all possible pairs  from A[] and store sums      of all possible pairs in aux[] */     int k = 0;     for (i = 0; i < n - 1; i++) {         for (j = i + 1; j < n; j++) {             aux[k].sum = arr[i] + arr[j];             aux[k].first = i;             aux[k].sec = j;             k++;         }     }     // Sort the aux[] array using     // library function for sorting     qsort(aux, size, sizeof(aux[0]), compare);     // Now start two index variables     // from two corners of array     // and move them toward each other.     i = 0;     j = size - 1;     while (i < size && j >= 0) {         if (             (aux[i].sum + aux[j].sum == X)             && noCommon(aux[i], aux[j])) {             cout << arr[aux[i].first]                  << ", " << arr[aux[i].sec]                  << ", " << arr[aux[j].first]                  << ", " << arr[aux[j].sec]                  << endl;             return;         }         else if (aux[i].sum + aux[j].sum < X)             i++;         else             j--;     } } // Driver code int main() {     int arr[] = { 10, 20, 30, 40, 1, 2 };     int n = sizeof(arr) / sizeof(arr[0]);     int X = 91;     findFourElements(arr, n, X);     return 0; } // This is code is contributed by rathbhupendra ```