本文介绍了从数组中查找总和等于给定数字的一对元素的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
给定 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更多推荐
从数组中查找总和等于给定数字的一对元素
发布评论