# 找到具有給定差異的一對 > 原文： [https://www.geeksforgeeks.org/find-a-pair-with-the-given-difference/](https://www.geeksforgeeks.org/find-a-pair-with-the-given-difference/) 給定一個未排序的數組和一個數字 n，請查找數組中是否存在一對差為 n 的元素。 **示例**： ``` Input: arr[] = {5, 20, 3, 2, 50, 80}, n = 78 Output: Pair Found: (2, 80) Input: arr[] = {90, 70, 20, 80, 50}, n = 45 Output: No Such Pair ``` 最簡單的方法是運行兩個循環，外循環選擇第一個元素（較小的元素），內循環查找外循環加上 n 拾取的元素。 該方法的時間復雜度為 O（n ^ 2）。 我們可以使用排序和二分搜索將時間復雜度提高到 O（nLogn）。 第一步是按升序對數組進行排序。 數組排序后，從左到右遍歷該數組，對于每個元素 arr [i]，在 arr [i + 1..n-1]中對 arr [i] + n 進行二分搜索。 如果找到該元素，則返回該對。 第一步和第二步都采用 O（nLogn）。 因此，總體復雜度為 O（nLogn）。 上述算法的第二步可以提高到`O(n)`。 第一步保持不變。 第二步的想法是采用兩個索引變量 i 和 j，分別將它們初始化為 0 和 1。 現在運行一個線性循環。 如果 arr [j] – arr [i]小于 n，我們需要尋找更大的 arr [j]，因此增加 j。 如果 arr [j] – arr [i]大于 n，則需要尋找更大的 arr [i]，因此增加 i。 感謝 Aashish Barnwal 提出了這種方法。 以下代碼僅用于算法的第二步，它假定數組已經排序。 ## C++ ```cpp // C++ program to find a pair with the given difference? #include <bits/stdc++.h> using namespace std; // The function assumes that the array is sorted? bool findPair(int arr[], int size, int n)? {? ????// Initialize positions of two elements? ????int i = 0;? ????int j = 1;? ????// Search for a pair? ????while (i < size && j < size)? ????{? ????????if (i != j && arr[j] - arr[i] == n)? ????????{? ????????????cout << "Pair Found: (" << arr[i] << ????????????????????????", " << arr[j] << ")";? ????????????return true;? ????????}? ????????else if (arr[j]-arr[i] < n)? ????????????j++;? ????????else ????????????i++;? ????}? ????cout << "No such pair";? ????return false;? }? // Driver program to test above function? int main()? {? ????int arr[] = {1, 8, 30, 40, 100};? ????int size = sizeof(arr)/sizeof(arr[0]);? ????int n = 60;? ????findPair(arr, size, n);? ????return 0;? }? // This is code is contributed by rathbhupendra ```