algorithm - 从数组中找到一对元素，其总和等于给定数

Question

给定 n 个整数数组和一个数字 X，找到所有唯一的元素对 (a,b)，其总和等于 X。

下面是我的解决方案，是O(nLog(n)+n)，但我不确定它是否是最优的。

int main(void)
{
    int arr [10] = {1,2,3,4,5,6,7,8,9,0};
    findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
    std::sort(arr, arr+len);
    int i = 0;
    int j = len -1;
    while( i < j){
        while((arr[i] + arr[j]) <= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            i++;
        }
        j--;
        while((arr[i] + arr[j]) >= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            j--;
        }
    }
}

Answer 1

此解决方案有 3 种方法:

令总和为T，n为数组大小

方法一:
这样做的天真方法是检查所有组合(n 选择 2)。这种详尽的搜索是 O(n²)。

方法 2:
更好的方法是对数组进行排序。这需要 O(n log n)
然后对于数组 A 中的每个 x， 使用二进制搜索查找 T-x。这将花费 O(nlogn)。
所以，整体搜索是 O(n log n)

方法 3:
最好的办法 将是将每个元素插入哈希表(不排序)。这将 O(n) 作为常数时间插入。
然后对于每个 x， 我们可以只查找它的补码 T-x，它的复杂度为 O(1)。
总的来说，这种方法的运行时间是 O(n)。

您可以引用更多 here 。谢谢。