给定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--; } } }
# Let arr be the given array. # And K be the give sum for i=0 to arr.length - 1 do hash(arr[i]) = i // key is the element and value is its index. end-for for i=0 to arr.length - 1 do if hash(K - arr[i]) != i // if Kth element exists and it's different then we found a pair print "pair i , hash(K - arr[i]) has sum K" end-if end-for