從數組中找到一對元素，其和等于給定的數字給定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--;
}
}}
3 回答
森欄
TA貢獻1810條經驗 獲得超5個贊
# Let arr be the given array.# And K be the give sumfor i=0 to arr.length - 1 do hash(arr[i]) = i // key is the element and value is its index.end-forfor i=0 to arr.length - 1 do if hash(K - arr[i]) != i // if K - ele exists and is different we found a pair print "pair i , hash(K - arr[i]) has sum K" end-ifend-for
添加回答
舉報
0/150
提交
取消