C++程序查找具有给定差异的一对元素

给定一个未排序的数组和一个数字n，查找数组中是否存在一对元素，它们的差是n。

例子：

输入：arr[] = {5, 20, 3, 2, 50, 80}，n = 78
输出：找到一对：(2, 80)

输入：arr[] = {90, 70, 20, 80, 50}，n = 45
输出：没有这样的一对元素

最简单的方法是运行两个循环，外部循环选取第一个元素（较小的元素），内部循环查找外部循环选取的元素加上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++ 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```

输出

找到一对：(40, 100)

高效的方法： 哈希也可以用于解决这个问题。我们首先创建一个空哈希表HT。然后我们在数组中遍历并将数组元素用作哈希键并将其输入到HT中。在遍历时，如果给定的差为0，则我们将检查任何元素是否发生多次。如果n！=0，则我们再次遍历数组，并在HT（哈希表）中查找 n + arr [i] 作为 arr [i] 和 n + arr [i] 之间的差异是n。

下面是上述方法的代码。

// C++程序，用于查找给定差值的一对数
#include <bits/stdc++.h>
using namespace std;
 
// 假定数组已经排序好了
bool findPair(int arr[], int size, int n)
{
    // 使用unordered_map进行哈希
    unordered_map<int, int> mp;
    for (int i = 0; i < size; i++) {
        // 使用数组元素作为哈希键，并将它们添加到哈希表中
        mp[arr[i]]++;
 
        // 当n等于0时，检查一个元素是不是出现了超过1次
        if (n==0 && mp[arr[i]] > 1)
            return true;
    }
 
    // 如果没有元素出现超过1次且差值仍为0，则返回false
    if (n==0)
        return false;
 
    // 遍历整个数组，检查arr[i]+n是否在哈希表中
    for (int i = 0; i <= size-1; i++)
    {
        if (mp[arr[i]+n])
        {
            cout << "Pair Found: "<< "(" << arr[i] << ", "<< n + arr[i] << ")";
            return true;
        }
    }
 
    cout << "No such pair";
    return false;
}
 
// 驱动程序，用于测试上述函数
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;
}
// 本代码由Pushpesh Raj提供。```

输出