从数组中查找总和等于给定数字的一对元素

本文介绍了从数组中查找总和等于给定数字的一对元素的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给定 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