# 從兩個排序的數組中找到最接近的對 > 原文： [https://www.geeksforgeeks.org/given-two-sorted-arrays-number-x-find-pair-whose-sum-closest-x/](https://www.geeksforgeeks.org/given-two-sorted-arrays-number-x-find-pair-whose-sum-closest-x/) 給定兩個已排序的數組和一個數字`x`，請找到總和最接近`x`的對，**該對具有每個數組中的元素**。 給定兩個數組`ar1[0…m-1]`和`ar2[0..n-1]`以及一個數字`x`，我們需要找到對`ar1[i] + ar2[j]`，使得`ar1[i] + ar2[j] – x`最小。 例： ``` Input: ar1[] = {1, 4, 5, 7}; ar2[] = {10, 20, 30, 40}; x = 32 Output: 1 and 30 Input: ar1[] = {1, 4, 5, 7}; ar2[] = {10, 20, 30, 40}; x = 50 Output: 7 and 40 ``` **我們強烈建議您最小化您的瀏覽器，然后自己嘗試。** 一個**簡單解決方案**是運行兩個循環。 外循環考慮第一個數組的每個元素，內循環檢查第二個數組中的對。 我們跟蹤`ar1[i] + ar2[j]`與`x`之間的最小差。 我們可以使用以下步驟在`O(n)`時間中完成。 1）使用合并排序的[合并過程](http://geeksquiz.com/merge-sort/)，將給定的兩個數組合并為大小為`m + n`的輔助數組。 合并時，請保留另一個大小為`m + n`的布爾數組，以指示合并數組中的當前元素是來自`ar1[]`還是`ar2[]`。 2）考慮合并數組，并使用[線性時間算法](http://geeksquiz.com/given-sorted-array-number-x-find-pair-array-whose-sum-closest-x/)找到總和最接近`x`的對。 我們還需要考慮僅具有`ar1[]`中一個元素和`ar2[]`中另一個元素的那些對，為此我們使用了布爾數組。 **我們可以一次通過并增加`O(1)`個空間嗎？** 的想法是從一個數組的左側開始，然后從另一數組的右側開始，并使用與上述方法的步驟 2 相同的算法。 以下是詳細的算法。 ``` 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 in ar1: l = 0 (b) Initialize second the rightmost index in ar2: r = n-1 3) Loop while l = 0 (a) If abs(ar1[l] + ar2[r] - sum) < diff then update diff and result (b) If (ar1[l] + ar2[r] < sum ) then l++ (c) Else r-- 4) Print the result. ``` 以下是此方法的實現。 ## C++ ```cpp // C++ program to find the pair from two sorted arays such // that the sum of pair is closest to a given number x #include <iostream> #include <climits> #include <cstdlib> using namespace std; // ar1[0..m-1] and ar2[0..n-1] are two given sorted arrays // and x is given number. This function prints the pair? from // both arrays such that the sum of the pair is closest to x. void printClosest(int ar1[], int ar2[], int m, int n, int x) { ????// Initialize the diff between pair sum and x. ????int diff = INT_MAX; ????// res_l and res_r are result indexes from ar1[] and ar2[] ????// respectively ????int res_l, res_r; ????// Start from left side of ar1[] and right side of ar2[] ????int l = 0, r = n-1; ????while (l<m && r>=0) ????{ ???????// If this pair is closer to x than the previously ???????// found closest, then update res_l, res_r and diff ???????if (abs(ar1[l] + ar2[r] - x) < diff) ???????{ ???????????res_l = l; ???????????res_r = r; ???????????diff = abs(ar1[l] + ar2[r] - x); ???????} ???????// If sum of this pair is more than x, move to smaller ???????// side ???????if (ar1[l] + ar2[r] > x) ???????????r--; ???????else? // move to the greater side ???????????l++; ????} ????// Print the result ????cout << "The closest pair is [" << ar1[res_l] << ", " ?????????<< ar2[res_r] << "] \n"; } // Driver program to test above functions int main() { ????int ar1[] = {1, 4, 5, 7}; ????int ar2[] = {10, 20, 30, 40}; ????int m = sizeof(ar1)/sizeof(ar1[0]); ????int n = sizeof(ar2)/sizeof(ar2[0]); ????int x = 38; ????printClosest(ar1, ar2, m, n, x); ????return 0; } ```