# 給定一個已排序的數組和一個數字 x，在數組中找到總和最接近 x 的對 > 原文： [https://www.geeksforgeeks.org/given-sorted-array-number-x-find-pair-array-whose-sum-closest-x/](https://www.geeksforgeeks.org/given-sorted-array-number-x-find-pair-array-whose-sum-closest-x/) 給定一個已排序的數組和一個數字 x，請在數組中找到總和最接近 x 的一對。 例子： ``` Input: arr[] = {10, 22, 28, 29, 30, 40}, x = 54 Output: 22 and 30 Input: arr[] = {1, 3, 4, 7, 10}, x = 15 Output: 4 and 10 ``` 一個簡單的解決方案是考慮每對，并跟蹤最接近的一對（對和和 x 之間的絕對差最小）。 最后打印最接近的一對。 該解決方案的時間復雜度為 `O(n^2)` 一個有效的解決方案可以在`O(n)`的時間內找到該對。 這個想法類似于此帖子的[的方法 2。 以下是詳細的算法。](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/) ``` 1) Initialize a variable diff as infinite (Diff is used to store the difference between pair and x). We need to find the minimum diff. 2) Initialize two index variables l and r in the given sorted array. (a) Initialize first to the leftmost index: l = 0 (b) Initialize second the rightmost index: r = n-1 3) Loop while l < r. (a) If abs(arr[l] + arr[r] - sum) < diff then update diff and result (b) Else if(arr[l] + arr[r] < sum ) then l++ (c) Else r-- ``` 以下是上述算法的實現。 ## C++ ```cpp // Simple C++ program to find the pair with sum closest to a given no. #include <bits/stdc++.h> using namespace std; // Prints the pair with sum closest to x void printClosest(int arr[], int n, int x) { ????int res_l, res_r;? // To store indexes of result pair ????// Initialize left and right indexes and difference between ????// pair sum and x ????int l = 0, r = n-1, diff = INT_MAX; ????// While there are elements between l and r ????while (r > l) ????{ ???????// Check if this pair is closer than the closest pair so far ???????if (abs(arr[l] + arr[r] - x) < diff) ???????{ ???????????res_l = l; ???????????res_r = r; ???????????diff = abs(arr[l] + arr[r] - x); ???????} ???????// If this pair has more sum, move to smaller values. ???????if (arr[l] + arr[r] > x) ???????????r--; ???????else // Move to larger values ???????????l++; ????} ????cout <<" The closest pair is " << arr[res_l] << " and " << arr[res_r]; } // Driver program to test above functions int main() { ????int arr[] =? {10, 22, 28, 29, 30, 40}, x = 54; ????int n = sizeof(arr)/sizeof(arr[0]); ????printClosest(arr, n, x); ????return 0; } ``` ## Java ```java // Java program to find pair with sum closest to x import java.io.*; import java.util.*; import java.lang.Math; class CloseSum { ????// Prints the pair with sum cloest to x ????static void printClosest(int arr[], int n, int x) ????{ ????????int res_l=0, res_r=0;? // To store indexes of result pair ????????// Initialize left and right indexes and difference between ????????// pair sum and x ????????int l = 0, r = n-1, diff = Integer.MAX_VALUE; ????????// While there are elements between l and r ????????while (r > l) ????????{ ????????????// Check if this pair is closer than the closest pair so far ????????????if (Math.abs(arr[l] + arr[r] - x) < diff) ????????????{ ???????????????res_l = l; ???????????????res_r = r; ???????????????diff = Math.abs(arr[l] + arr[r] - x); ????????????} ????????????// If this pair has more sum, move to smaller values. ????????????if (arr[l] + arr[r] > x) ???????????????r--; ????????????else // Move to larger values ???????????????l++; ????????} ????System.out.println(" The closest pair is "+arr[res_l]+" and "+ arr[res_r]); } ????// Driver program to test above function ????public static void main(String[] args) ????{ ????????int arr[] =? {10, 22, 28, 29, 30, 40}, x = 54; ????????int n = arr.length; ????????printClosest(arr, n, x);???????? ????} } /*This code is contributed by Devesh Agrawal*/ ``` ## Python3 ```py # Python3 program to find the pair # with sum? # closest to a given no. # A sufficiently large value greater # than any? # element in the input array MAX_VAL = 1000000000 #Prints the pair with sum closest to x def printClosest(arr, n, x): ????# To store indexes of result pair ????res_l, res_r = 0, 0 ????#Initialize left and right indexes ????# and difference between ????# pair sum and x ????l, r, diff = 0, n-1, MAX_VAL ????# While there are elements between l and r ????while r > l: ????????# Check if this pair is closer than the? ????????# closest pair so far ????????if abs(arr[l] + arr[r] - x) < diff: ????????????res_l = l ????????????res_r = r ????????????diff = abs(arr[l] + arr[r] - x) ????????if arr[l] + arr[r] > x: ????????# If this pair has more sum, move to? ????????# smaller values. ????????????r -= 1 ????????else: ????????# Move to larger values ????????????l += 1 ????print('The closest pair is {} and {}' ?????????.format(arr[res_l], arr[res_r])) # Driver code to test above if __name__ == "__main__": ????arr = [10, 22, 28, 29, 30, 40] ????n = len(arr) ????x=54 ????printClosest(arr, n, x) # This code is contributed by Tuhin Patra ``` ## C# ```cs // C# program to find pair with sum closest to x using System; class GFG { ????// Prints the pair with sum cloest to x ????static void printClosest(int []arr, int n, int x) ????{ ????????// To store indexes of result pair ????????int res_l = 0, res_r = 0;? ????????// Initialize left and right indexes and? ????????// difference between pair sum and x ????????int l = 0, r = n-1, diff = int.MaxValue; ????????// While there are elements between l and r ????????while (r > l) ????????{ ????????????// Check if this pair is closer than the ????????????// closest pair so far ????????????if (Math.Abs(arr[l] + arr[r] - x) < diff) ????????????{ ????????????????res_l = l; ????????????????res_r = r; ????????????????diff = Math.Abs(arr[l] + arr[r] - x); ????????????} ????????????// If this pair has more sum, move to ????????????// smaller values. ????????????if (arr[l] + arr[r] > x) ????????????r--; ????????????else // Move to larger values ????????????l++; ????????} ????????Console.Write(" The closest pair is " + ?????????????????arr[res_l] + " and " + arr[res_r]); ????} ????// Driver program to test above function ????public static void Main() ????{ ????????int []arr = {10, 22, 28, 29, 30, 40}; ????????int x = 54; ????????int n = arr.Length; ????????printClosest(arr, n, x);????? ????} } // This code is contributed by nitin mittal. ``` ## PHP ```php <?php // Simple PHP program to find the // pair with sum closest to a? // given no. // Prints the pair with // sum closest to x function printClosest($arr, $n, $x) { ????// To store indexes ????// of result pair ????$res_l; ????$res_r;? ????// Initialize left and right? ????// indexes and difference between ????// pair sum and x ????$l = 0;? ????$r = $n - 1; ????$diff = PHP_INT_MAX; ????// While there are elements ????// between l and r ????while ($r > $l) ????{ ????????// Check if this pair is closer? ????????// than the closest pair so far ????????if (abs($arr[$l] + $arr[$r] - $x) <? ??????????????????????????????????????$diff) ????????{ ????????????$res_l = $l; ????????????$res_r = $r; ????????????$diff = abs($arr[$l] + $arr[$r] - $x); ????????} ????????// If this pair has more sum,? ????????// move to smaller values. ????????if ($arr[$l] + $arr[$r] > $x) ????????????$r--; ????????// Move to larger values ????????else? ????????????$l++; ????} ????echo " The closest pair is "? ?????????, $arr[$res_l] ," and "? ?????????, $arr[$res_r]; } ????// Driver Code ????$arr = array(10, 22, 28, 29, 30, 40);? ????$x = 54; ????$n = count($arr); ????printClosest($arr, $n, $x); // This code is contributed by anuj_67\. ?> ``` **輸出**： ``` The closest pair is 22 and 30 ```