# 找到四個總和為給定值的元素| 系列 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 ```