射程資金

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到哈希表。