給定數組 A []和數字 x，請檢查 A []中的對，總和為 x · GeeksForGeeks 中文系列教程

# 給定數組 A []和數字 x，請檢查 A []中的對，總和為 x > 原文： [https://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/](https://www.geeksforgeeks.org/write-a-c-program-that-given-a-set-a-of-n-numbers-and-another-number-x-determines-whether-or-not-there-exist-two-elements-in-s-whose-sum-is-exactly-x/) 編寫一個程序，給定 n 個數字的數組 A []和另一個數字 x，確定 S 中是否存在兩個元素的總和恰好是 x。 **示例**： ``` Input: arr[] = {0, -1, 2, -3, 1} sum = -2 Output: -3, 1 If we calculate the sum of the output, 1 + (-3) = -2 Input: arr[] = {1, -2, 1, 0, 5} sum = 0 Output: -1 No valid pair exists. ``` **方法 1 **：排序和兩指針技術。 **方法**：解決此問題的棘手方法可以是使用兩指針技術。但是對于使用兩個指針技術，必須對數組進行排序。一旦對數組排序，就可以采用兩個指針分別標記數??組的開始和結束。如果**的總和大于這兩個元素的總和**，則向左移動指針以增加所需總和的值；如果總和**小于**所需的總和，則向右移動減小值的指針。讓我們通過一個例子來理解這一點。 > 令數組為{1、4、45、6、10，-8}，求和為 16 > > 對數組 > 排序后，A = {-8、1、4、6、10、45} > > 現在，當對的總和小于所需的總和時，將“ l”增加，而當對的總和大于所需的總和時，將“ r”減少。 > 這是因為，當總和小于所需總和時，為了獲得可以增加配對總和的數字，請從左向右移動（也對數組進行排序），從而“ l ++”，反之亦然。 > > 初始化 l = 0，r = 5 > A [l] + A [r]（-8 + 45）> 16 = >遞減 r。現在 r = 4 > A [l] + A [r]（-8 + 10）增量 l。現在 l = 1 > A [l] + A [r]（1 + 10）遞增 l。現在 l = 2 > A [l] + A [r]（4 + 10）遞增 l。現在 l = 3 > A [l] + A [r]（6 + 10）== 16 = >找到候選對象（返回 1） **注意**：如果有給定總和的一對以上，則此算法僅報告一個。可以很容易地對此進行擴展。 **算法**： 1. hasArrayTwoCandidates（A []??，ar_size，sum） 2. 以非降序對數組進行排序。 3. 初始化兩個索引變量以在排序的數組中找到候選元素。 1. 首先初始化到最左邊的索引：l = 0 2. 初始化第二個最右邊的索引：r = ar_size-1 4. l < r 時循環播放。 1. 如果（A [l] + A [r] ==和），則返回 1 2. 否則 if（A [l] + A [r] < sum）然后 l ++ 3. 其他 r– 5. 整個數組中沒有候選者-返回 0 ## C++ ```cpp // C++ program to check if given array // has 2 elements whose sum is equal // to the given value #include <bits/stdc++.h> using namespace std; // Function to check if array has 2 elements // whose sum is equal to the given value bool hasArrayTwoCandidates(int A[], int arr_size, ???????????????????????????int sum) { ????int l, r; ????/* Sort the elements */ ????sort(A, A + arr_size); ????/* Now look for the two candidates in? ???????the sorted array*/ ????l = 0; ????r = arr_size - 1; ????while (l < r) { ????????if (A[l] + A[r] == sum) ????????????return 1; ????????else if (A[l] + A[r] < sum) ????????????l++; ????????else // A[i] + A[j] > sum ????????????r--; ????} ????return 0; } /* Driver program to test above function */ int main() { ????int A[] = { 1, 4, 45, 6, 10, -8 }; ????int n = 16; ????int arr_size = sizeof(A) / sizeof(A[0]); ????// Function calling ????if (hasArrayTwoCandidates(A, arr_size, n)) ????????cout << "Array has two elements" ????????????????" with given sum"; ????else ????????cout << "Array doesn't have two" ????????????????" elements with given sum"; ????return 0; } ``` ## C ``` // C program to check if given array // has 2 elements whose sum is equal // to the given value #include <stdio.h> #define bool int void quickSort(int*, int, int); bool hasArrayTwoCandidates( ????int A[], int arr_size, int sum) { ????int l, r; ????/* Sort the elements */ ????quickSort(A, 0, arr_size - 1); ????/* Now look for the two candidates in the sorted? ???????array*/ ????l = 0; ????r = arr_size - 1; ????while (l < r) { ????????if (A[l] + A[r] == sum) ????????????return 1; ????????else if (A[l] + A[r] < sum) ????????????l++; ????????else // A[i] + A[j] > sum ????????????r--; ????} ????return 0; } /* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING? ????PURPOSE */ void exchange(int* a, int* b) { ????int temp; ????temp = *a; ????*a = *b; ????*b = temp; } int partition(int A[], int si, int ei) { ????int x = A[ei]; ????int i = (si - 1); ????int j; ????for (j = si; j <= ei - 1; j++) { ????????if (A[j] <= x) { ????????????i++; ????????????exchange(&A[i], &A[j]); ????????} ????} ????exchange(&A[i + 1], &A[ei]); ????return (i + 1); } /* Implementation of Quick Sort A[] --> Array to be sorted si? --> Starting index ei? --> Ending index */ void quickSort(int A[], int si, int ei) { ????int pi; /* Partitioning index */ ????if (si < ei) { ????????pi = partition(A, si, ei); ????????quickSort(A, si, pi - 1); ????????quickSort(A, pi + 1, ei); ????} } /* Driver program to test above function */ int main() { ????int A[] = { 1, 4, 45, 6, 10, -8 }; ????int n = 16; ????int arr_size = 6; ????if (hasArrayTwoCandidates(A, arr_size, n)) ????????printf("Array has two elements with given sum"); ????else ????????printf("Array doesn't have two elements with given sum"); ????getchar(); ????return 0; } ``` ## Java ```java // Java program to check if given array // has 2 elements whose sum is equal // to the given value import java.util.*; class GFG { ????// Function to check if array has 2 elements ????// whose sum is equal to the given value ????static boolean hasArrayTwoCandidates( ????????int A[], ????????int arr_size, int sum) ????{ ????????int l, r; ????????/* Sort the elements */ ????????Arrays.sort(A); ????????/* Now look for the two candidates? ????????in the sorted array*/ ????????l = 0; ????????r = arr_size - 1; ????????while (l < r) { ????????????if (A[l] + A[r] == sum) ????????????????return true; ????????????else if (A[l] + A[r] < sum) ????????????????l++; ????????????else // A[i] + A[j] > sum ????????????????r--; ????????} ????????return false; ????} ????// Driver code ????public static void main(String args[]) ????{ ????????int A[] = { 1, 4, 45, 6, 10, -8 }; ????????int n = 16; ????????int arr_size = A.length; ????????// Function calling ????????if (hasArrayTwoCandidates(A, arr_size, n)) ????????????System.out.println("Array has two " ???????????????????????????????+ "elements with given sum"); ????????else ????????????System.out.println("Array doesn't have " ???????????????????????????????+ "two elements with given sum"); ????} } ``` ## Python ``` # Python program to check for the sum condition to be satisified def hasArrayTwoCandidates(A, arr_size, sum): ????# sort the array ????quickSort(A, 0, arr_size-1) ????l = 0 ????r = arr_size-1 ????# traverse the array for the two elements ????while l<r: ????????if (A[l] + A[r] == sum): ????????????return 1 ????????elif (A[l] + A[r] < sum): ????????????l += 1 ????????else: ????????????r -= 1 ????return 0 # Implementation of Quick Sort # A[] --> Array to be sorted # si? --> Starting index # ei? --> Ending index def quickSort(A, si, ei): ????if si < ei: ????????pi = partition(A, si, ei) ????????quickSort(A, si, pi-1) ????????quickSort(A, pi + 1, ei) # Utility function for partitioning the array(used in quick sort) def partition(A, si, ei): ????x = A[ei] ????i = (si-1) ????for j in range(si, ei): ????????if A[j] <= x: ????????????i += 1 ????????????# This operation is used to swap two variables is python ????????????A[i], A[j] = A[j], A[i] ????????A[i + 1], A[ei] = A[ei], A[i + 1] ????return i + 1 # Driver program to test the functions A = [1, 4, 45, 6, 10, -8] n = 16 if (hasArrayTwoCandidates(A, len(A), n)): ????print("Array has two elements with the given sum") else: ????print("Array doesn't have two elements with the given sum") ## This code is contributed by __Devesh Agrawal__ ``` ## C# ```cs // C# program to check for pair // in A[] with sum as x using System; class GFG { ????static bool hasArrayTwoCandidates(int[] A, ??????????????????????????????????????int arr_size, int sum) ????{ ????????int l, r; ????????/* Sort the elements */ ????????sort(A, 0, arr_size - 1); ????????/* Now look for the two candidates? ????????in the sorted array*/ ????????l = 0; ????????r = arr_size - 1; ????????while (l < r) { ????????????if (A[l] + A[r] == sum) ????????????????return true; ????????????else if (A[l] + A[r] < sum) ????????????????l++; ????????????else // A[i] + A[j] > sum ????????????????r--; ????????} ????????return false; ????} ????/* Below functions are only to sort the? ????array using QuickSort */ ????/* This function takes last element as pivot, ????places the pivot element at its correct ????position in sorted array, and places all ????smaller (smaller than pivot) to left of ????pivot and all greater elements to right ????of pivot */ ????static int partition(int[] arr, int low, int high) ????{ ????????int pivot = arr[high]; ????????// index of smaller element ????????int i = (low - 1); ????????for (int j = low; j <= high - 1; j++) { ????????????// If current element is smaller ????????????// than or equal to pivot ????????????if (arr[j] <= pivot) { ????????????????i++; ????????????????// swap arr[i] and arr[j] ????????????????int temp = arr[i]; ????????????????arr[i] = arr[j]; ????????????????arr[j] = temp; ????????????} ????????} ????????// swap arr[i+1] and arr[high] (or pivot) ????????int temp1 = arr[i + 1]; ????????arr[i + 1] = arr[high]; ????????arr[high] = temp1; ????????return i + 1; ????} ????/* The main function that? ????implements QuickSort() ????arr[] --> Array to be sorted, ????low --> Starting index, ????high --> Ending index */ ????static void sort(int[] arr, int low, int high) ????{ ????????if (low < high) { ????????????/* pi is partitioning index, arr[pi]? ????????????is now at right place */ ????????????int pi = partition(arr, low, high); ????????????// Recursively sort elements before ????????????// partition and after partition ????????????sort(arr, low, pi - 1); ????????????sort(arr, pi + 1, high); ????????} ????} ????// Driver code ????public static void Main() ????{ ????????int[] A = { 1, 4, 45, 6, 10, -8 }; ????????int n = 16; ????????int arr_size = 6; ????????if (hasArrayTwoCandidates(A, arr_size, n)) ????????????Console.Write("Array has two elements" ??????????????????????????+ " with given sum"); ????????else ????????????Console.Write("Array doesn't have " ??????????????????????????+ "two elements with given sum"); ????} } // This code is contributed by Sam007 ``` ## PHP ```php <?php // PHP program to check if given? // array has 2 elements whose sum? // is equal to the given value // Function to check if array has? // 2 elements whose sum is equal // to the given value function hasArrayTwoCandidates($A, $arr_size, ????????????????????????????????????????$sum) { ????$l; $r; ????/* Sort the elements */ ????//sort($A, A + arr_size); ????sort($A); ????/* Now look for the two candidates? ????in the sorted array*/ ????$l = 0; ????$r = $arr_size - 1;? ????while ($l < $r) ????{ ????????if($A[$l] + $A[$r] == $sum) ????????????return 1;? ????????else if($A[$l] + $A[$r] < $sum) ????????????$l++; ????????else // A[i] + A[j] > sum ????????????$r--; ????}? ????return 0; } // Driver Code $A = array (1, 4, 45, 6, 10, -8); $n = 16; $arr_size = sizeof($A); // Function calling if(hasArrayTwoCandidates($A, $arr_size, $n)) ????echo "Array has two elements " . ???????????????????"with given sum"; else ????echo "Array doesn't have two " .? ??????????"elements with given sum"; // This code is contributed by m_kit ?> ``` **輸出**： ``` Array has two elements with the given sum ``` **復雜度分析**： * **時間復雜度**：取決于我們使用哪種排序算法。 * 如果使用合并排序或堆排序，則在最壞的情況下使用（-）（nlogn）。 * 如果使用快速排序，則在最壞的情況下為 O（n ^ 2）。 * **輔助空間**：這也取決于排序算法。輔助空間是用于合并排序的`O(n)`和用于堆排序的`O(1)`。 **方法 2 **： [散列](http://www.geeksforgeeks.org/hashing-data-structure/)。 **方法**：通過使用哈希技術可以有效解決此問題。使用 **hash_map** 檢查當前數組值 **x（let）**，如果存在值 **target_sum-x** ，將其添加到前者后得到 **] target_sum** 。這可以在恒定時間內完成。讓我們看下面的例子。 > arr [] = {0，-1，2，-3，1} > sum = -2 > 現在開始遍歷： > 步驟 1：對于'0'，沒有有效的數字'-2' 因此將“ 0”存儲在 hash_map 中。 > 步驟 2：對于“ -1”，沒有有效的數字“ -1”，因此將“ -1”存儲在 hash_map 中。 > 步驟 3：對于“ 2”，沒有有效的數字“ -4”，因此將“ 2”存儲在 hash_map 中。 > 步驟 4：對于“ -3”，沒有有效的數字“ 1”，因此請將“ -3”存儲在 hash_map 中。 > 步驟 5：對于“ 1”，有一個有效數字“ -3”，因此答案為 1，-3 **算法**： 1. 初始化一個空的哈希表 s。 2. 對 A []中的每個元素 A [i]執行以下操作 1. 如果設置了 s [x – A [i]]，則打印該對（A [i]，x – A [i]） 2. 將 A [i]插入 s。 **偽代碼**： ``` unordered_set s for(i=0 to end) if(s.find(target_sum - arr[i]) == s.end) insert(arr[i] into s) else print arr[i], target-arr[i] ``` ## C++ ``` // C++ program to check if given array // has 2 elements whose sum is equal // to the given value #include <bits/stdc++.h> using namespace std; void printPairs(int arr[], int arr_size, int sum) { ????unordered_set<int> s; ????for (int i = 0; i < arr_size; i++) { ????????int temp = sum - arr[i]; ????????if (s.find(temp) != s.end()) ????????????cout << "Pair with given sum " ?????????????????<< sum << " is ( ???????????????????????????" << arr[i] << ", ????????????????"? ????????????????????<< temp << ")" << endl; ????????s.insert(arr[i]); ????} } /* Driver program to test above function */ int main() { ????int A[] = { 1, 4, 45, 6, 10, 8 }; ????int n = 16; ????int arr_size = sizeof(A) / sizeof(A[0]); ????// Function calling ????printPairs(A, arr_size, n); ????return 0; } ``` ## C ``` // C++ program to check if given array // has 2 elements whose sum is equal // to the given value // Works only if range elements is limited #include <stdio.h> #define MAX 100000 void printPairs(int arr[], int arr_size, int sum) { ????int i, temp; ????/*initialize hash set as 0*/ ????bool s[MAX] = { 0 }; ????for (i = 0; i < arr_size; i++) { ????????temp = sum - arr[i]; ????????if (s[temp] == 1) ????????????printf( ????????????????"Pair with given sum %d is (%d, %d) n", ????????????????sum, arr[i], temp); ????????s[arr[i]] = 1; ????} } /* Driver program to test above function */ int main() { ????int A[] = { 1, 4, 45, 6, 10, 8 }; ????int n = 16; ????int arr_size = sizeof(A) / sizeof(A[0]); ????printPairs(A, arr_size, n); ????getchar(); ????return 0; } ``` ## Java ```java // Java implementation using Hashing import java.io.*; import java.util.HashSet; class PairSum { ????static void printpairs(int arr[], int sum) ????{ ????????HashSet<Integer> s = new HashSet<Integer>(); ????????for (int i = 0; i < arr.length; ++i) { ????????????int temp = sum - arr[i]; ????????????// checking for condition ????????????if (s.contains(temp)) { ????????????????System.out.println( ????????????????????"Pair with given sum " ????????????????????+ sum + " is (" + arr[i] ????????????????????+ ", " + temp + ")"); ????????????} ????????????s.add(arr[i]); ????????} ????} ????// Main to test the above function ????public static void main(String[] args) ????{ ????????int A[] = { 1, 4, 45, 6, 10, 8 }; ????????int n = 16; ????????printpairs(A, n); ????} } // This article is contributed by Aakash Hasija ``` ## Python ``` # Python program to find if there are # two elements wtih given sum # function to check for the given sum # in the array def printPairs(arr, arr_size, sum): ????# Create an empty hash set ????s = set() ????for i in range(0, arr_size): ????????temp = sum-arr[i] ????????if (temp in s): ????????????print "Pair with given sum "+ str(sum) + " is (" + str(arr[i]) + ", " + str(temp) + ")" ????????s.add(arr[i]) # driver program to check the above function A = [1, 4, 45, 6, 10, 8] n = 16 printPairs(A, len(A), n) # This code is contributed by __Devesh Agrawal__ ``` ## C# ``` // C# implementation using Hashing using System; using System.Collections.Generic; class GFG { ????static void printpairs(int[] arr, ???????????????????????????int sum) ????{ ????????HashSet<int> s = new HashSet<int>(); ????????for (int i = 0; i < arr.Length; ++i) { ????????????int temp = sum - arr[i]; ????????????// checking for condition ????????????if (s.Contains(temp)) { ????????????????Console.Write("Pair with given sum " + sum + " is (" + arr[i] + ", " + temp + ")"); ????????????} ????????????s.Add(arr[i]); ????????} ????} ????// Driver Code ????static void Main() ????{ ????????int[] A = new int[] { 1, 4, 45, ??????????????????????????????6, 10, 8 }; ????????int n = 16; ????????printpairs(A, n); ????} } // This code is contributed by // Manish Shaw(manishshaw1) ``` **輸出**： ``` Pair with given sum 16 is (10, 6) ``` **Complexity Analysis:** * **時間復雜度**：`O(n)`。由于整個數組僅需要遍歷一次。 * **輔助空間**：`O(n)`。由于哈希映射已用于存儲數組元素。 **注意**：如果數字范圍包含負數，則也可以正常工作。 **相關問題**： * [給定兩個未排序的數組，找到總和為 x 的所有對。](https://www.geeksforgeeks.org/given-two-unsorted-arrays-find-pairs-whose-sum-x/) * [具有給定總和的計數對](https://www.geeksforgeeks.org/count-pairs-with-given-sum/) * [計算所有等于 k 的不同對](https://www.geeksforgeeks.org/count-pairs-difference-equal-k/) 如果您發現上述任何代碼/算法不正確，或者找到其他解決相同問題的方法，請寫評論。