相关疑难解决方法(0)

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

我们需要在数组中找到一对数,其总和等于给定值.

A = {6,4,5,7,9,1,2}

Sum = 10然后对是 - {6,4},{9,1}

我有两个解决方案.

• O(nlogn)解决方案 - 使用2个迭代器(开始和结束)排序+校验和.
• 一个O(n)解决方案 - 散列数组.然后检查sum-hash[i]哈希表中是否存在.

但是,问题在于虽然第二种解决方案是O(n)时间,但也使用O(n)空间.

所以,我想知道我们是否可以在O(n)时间和O(1)空间中完成它.这不是功课!