2-sum算法具有一定范围的和的变体 [英] Variant of the 2-sum algorithm with a range of sums

问题描述

问题陈述如下:

此问题的目标是实现2-SUM算法的一种变体.

The goal of this problem is to implement a variant of the 2-SUM algorithm.

文件包含一百万个正负整数(可能会重复！).这是您的整数数组，文件的第i行指定了数组的第i个条目.

The file contains 1 million integers, both positive and negative (there might be some repetitions!).This is your array of integers, with the ith row of the file specifying the ith entry of the array.

您的任务是计算区间[-10000,10000](含)中的目标值t的数量，以使输入文件中存在满足x + y = t的不同数量x，y.

Your task is to compute the number of target values t in the interval [-10000,10000] (inclusive) such that there are distinct numbers x,y in the input file that satisfy x+y=t.

输入数字答案(0到20001之间的整数).

Write your numeric answer (an integer between 0 and 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].

It gives the correct answer, but, it is too slow. How can i improve the solution. The input numbers are in the range [-99999887310 ,99999662302].

推荐答案

源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:

Test file 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更改为哈希表.

For huge range, change array arr to hashtable.

这篇关于2-sum算法具有一定范围的和的变体的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！