从数组中查找总和等于给定数字的一对元素 [英] Find a pair of elements from an array whose sum equals a given number

问题描述

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

Given array of n integers and given a number X, find all the unique pairs of elements (a,b), whose summation is equal to X.

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

The following is my solution, it is O(nLog(n)+n), but I am not sure whether or not it is optimal.

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--;
        }
    }
}

推荐答案

# Let arr be the given array.
# And K be the give sum


for i=0 to arr.length - 1 do
  # key is the element and value is its index.
  hash(arr[i]) = i  
end-for

for i=0 to arr.length - 1 do
  # if K-th element exists and it's different then we found a pair
  if hash(K - arr[i]) != i  
    print "pair i , hash(K - arr[i]) has sum K"
  end-if
end-for

这篇关于从数组中查找总和等于给定数字的一对元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！