给定一个已排序的数组和一个数字 x，在数组中找到总和最接近 x 的对 · GeeksForGeeks 中文系列教程

# 给定一个已排序的数组和一个数字 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 ```