找到的一对元件从一个数组，其总和等于给定数量的 [英] Find a pair of elements from an array whose sum equals a given number

问题描述

给定n整数数组，并且获得数X，发现所有的唯一对elemens的（A，B），其总和是等于X

以下是我的解决方案，这是O（n日志（N）+ N），但我不知道是否是最优的。感谢您的意见。

INT主要（无效） {     INT改编[10] = {1,2,3,4,5,6,7,8,9,0};     findpair（ARR，10，7）; } 无效findpair（INT改编[]，INT LEN，INT和） {     性病::排序（ARR，编曲+ LEN）;     INT I = 0;     INT J = len个-1;     而（I＆LT; j）条{         而（（ARR [I] +常用3 [J]）＆LT; = SUM和放大器;＆安培; I＆LT; j）条         {             如果（（ARR [I] +常用3 [J]）==总和）                 COUT＆LT;＆LT; （＆其中;＆其中;常用3 [1] - ;＆所述;，＆其中;＆其中;常用3 [j]的＆其中;＆所述;）＆其中;＆其中; ENDL;             我++;         }         j--;         而（（ARR [I] +常用3 [J]。）＆GT; = SUM和放大器;＆安培; I＆LT; j）条         {             如果（（ARR [I] +常用3 [J]）==总和）                 COUT＆LT;＆LT; （＆其中;＆其中;常用3 [1] - ;＆所述;，＆其中;＆其中;常用3 [j]的＆其中;＆所述;）＆其中;＆其中; ENDL;             j--;         }     } }

解决方案

＃让ARR是给定的数组。 ＃和K是给予总和 对于i = 0至arr.length - 1做   哈希（ARR [I]）= I //关键是元素和价值是它的索引。 最终的 对于i = 0至arr.length - 1做   如果哈希！（K - 常用3 [I]）= I //在K - ELE存在，不同的是，我们发现一对     打印对我，散列（K - 常用3 [I]）的总和K   最终，如果 最终的

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

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

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 K - ele exists and is different we found a pair
    print "pair i , hash(K - arr[i]) has sum K"
  end-if
end-for

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