射程资金

Question

的各种版本2和算法的问题说明如下：

这个问题的目标是实现2和算法的变体。

该文件包含100万个整数，包括正数和负数（可能有一些重复！）。这是整数数组，其中第i行指定数组的第i个条目。

您的任务是计算区间[-10000,10000]（含）内的目标值数t，以使输入文件中有不同数x，y满足x + y = t。

编写数字答案（0到20001之间的整数）。

我实现了一个天真的解决方案：

#include <iostream> 
#include <fstream> 
#include <unordered_set> 
#include <vector> 
#include <algorithm> 

#define FILE "2sum.txt" 
#define LEFT -10000 
#define RIGHT 10000 

using namespace std; 

class cal_2sum{ 
    int count; 
    unordered_set<long> hashT; 
    vector<long> array; 

public: 
    cal_2sum(){ 
     count = 0; 
    } 
    int getCount(){ 
     return this->count; 
    } 
    int calculate(string filename,int left, int right){ 
     ifstream file(filename); 

     long num; 
     while(file>>num){ 
      hashT.insert(num); 

     } 
     for(auto it = hashT.begin(); it != hashT.end(); ++it) 
      array.push_back(*it); 
     sort(array.begin(),array.end()); 

     for(long target = left; target<=right; target++){ 
      bool found = false; 
      for(auto it = array.begin(); it != array.end(); ++it){ 
       long otherHalf = target - (*it); 
       auto verdict = hashT.find(otherHalf); 
       if(verdict != hashT.end() && (*verdict) != (*it)){ 
        found = true; 
        break; 
       } 
      } 
      if(found == true) 
       count++; 
      cout<<count<<endl; 
     } 
    } 

}; 


int main(){ 
    cal_2sum res; 
    res.calculate(FILE,LEFT,RIGHT); 
    cout<<res.getCount()<<endl; 

    return 0; 
} 

它给出了正确的答案，但是，实在是太慢了。我如何改进解决方案。 输入数字在[-99999887310 ，99999662302]范围内。

Answer 1

源2sum.c：

#include <stdio.h> 
#include <strings.h> 

#define MAXVAL 10000 

int main(int argc, char **argv) { 
    // init vars 
    int i, t, rc = 0; 
    unsigned arr[2 * MAXVAL + 1], *p0 = arr + MAXVAL; 
    bzero(arr, sizeof(arr)); 

    FILE *f = fopen(argv[1], "r"); 
    if(f == NULL) 
    return -1; // unable to open file 

    char buf[100]; 
    while(fgets(buf, sizeof(buf), f)) 
    p0[atoi(buf)]++; 

    t = atoi(argv[2]); // Target sum 

    for(i = -MAXVAL; i <= MAXVAL; i++) 
    rc += p0[i] * p0[t - i]; 

    printf("Combinations: %d\n", rc >> 1); 
    return fclose(f); 
} 

测试文件2sum.txt：

5 
5 
10 
10 
1 
-5 

执行命令的例子：

$ ./a.out 2sum.txt 0 
Combinations: 2 

$ ./a.out 2sum.txt 15 
Combinations: 4 

$ ./a.out 2sum.txt 13 
Combinations: 0 

对于巨大范围，改变阵列ARR到哈希表。