c++ - 在方程 x+y=t 中搜索 y 时如何获得不同的值？

Question

我正在研究 2 和问题，我在其中搜索 t-x(或 y)以查找是否 x + y = t 以及是否有一个值添加到 x 使和成为 t。

T 是从 -10000 到 10000 的所有值。我实现了一个 nlogn 解决方案，因为我不知道如何使用哈希表(我看到的大多数示例都是字符而不是整数)。我的nlogn解决方案是使用快速排序对数字进行排序，然后使用二进制搜索来搜索t-x。

我相信我的问题是目前我也在输入重复项。例如，在数组 {1,2,3,4,5} 中，如果 t 为 5，则 2+3 和 1 + 4 等于 5，但它应该只给出 1，而不是 2。换句话说，我需要得到 t 中的所有“不同”或不同的总和。我相信那是我的代码有问题的地方。据说 x!=y 行应该使它与众不同，尽管我不明白如何实现，甚至在实现时仍然给我错误的答案。

这是包含测试用例的数据文件的链接: http://bit.ly/1JcLojP100的答案是42，1000是486，10000是496，1000000是519。我的输出是84,961,1009，我没有测试100万。

对于我的代码，您可以假设二进制搜索和快速排序已正确实现。快速排序应该给你它比较事物的次数，但我从来没有想过如何返回两件事(比较和索引)。

#include <stdio.h>    
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <string>
#include <ctime>
#include <cstdlib>
#include <cmath>
#include <cctype>
using namespace std;

long long binary_search(long long array[],long long first,long long last, long long search_key)
{
    long long index;    
    if (first > last)
        index = -1;
    else
    {
        long long mid = (first + last)/2;
        if (search_key == array[mid])
            index = mid;
        else
            if (search_key < array[mid])
                index = binary_search(array,first, mid-1, search_key);
            else
                index = binary_search(array, mid+1, last, search_key);
    } // end if
    return index;
}// end binarySearch

long long partition(long long arr[],long long l, long long h)
{
    long long i;
    long long p;
    long long firsthigh;
    p = h;
    firsthigh = l;
    long long temporary = 0;

    for (i=(l +0); i<= h; i++)
    {
        if (arr[i] < arr[p])
        {
        long long temp2 = 0;
        temp2 = arr[i];
        arr[i] = arr[firsthigh];
        arr[firsthigh] = temp2;
        firsthigh ++;
    }
}
temporary = arr[p];
arr[p] = arr[firsthigh];
arr[firsthigh] = temporary;
    return(firsthigh);
}

long long quicksort(long long arr[], long long l, long long h)
{
    long long p;                  /* index of partition */
        if ((h-l)>0)
        {
            p = partition(arr,l,h);
            quicksort(arr,l,p-1);
            quicksort(arr,p+1,h);
        }
        if(h == l)
            return 1;
        else
            return 0;
    }
    int main(int argc, const char * argv[])
    {
        long long array[1000000] = {0};
    long long t;
    long long count = 0;
    ifstream inData;
    inData.open("/Users/SeanYeh/downloads/100.txt");
    cout<<"part 1"<<endl;
    for (long long i=0;i<100;i++)
    {
        inData >> array[i];
        //cout<<array[i]<<endl;
    }inData.close();
    cout<<"part 2"<<endl;
    quicksort(array,0,100);
    cout<<"part 3"<<endl;
    for(t = 10000;t >= -10000;t--)
    {
    for(int x = 0;x<100;x++)
    {
        long long exists = binary_search(array,0,100,t-array[x]);
        if (exists >= 0)
        {
            count++;
        }
    }
}
cout<<"The value of count is: "<<count<<endl;
}

Answer 1

为避免重复，您需要将二进制搜索范围从 [0,n] 更改为 [x+1,n]。此外，一旦您发现存在总和，就会跳出循环。

long long exists=binary_search(array, x+1, 100, t-array[x]);
if(exists >= 0)
{
    count++;
    break;
}