Given 1 million integers, both positive and negative(there might be repetitions and number of digits in a number may be as large as 12 digits).
The task is to compute the number of target values t in the interval [-10000,10000] (inclusive) such that there are distinct numbers x,y from the given numbers that satisfy x+y=t.
I have a O(m*n) [m=20001 and n=10^6] implementation using hash(via unordered_set in C++) but it’s turning out to be too slow for the given data. Any feasible ideas approaches for the problem preferably which could be implemented in c++14. If anyone is interested in solving the input file containing the 1 million integers:
https://drive.google.com/open?id=185h63XZ4EnwojvLIfKZqBxdpgr0-JF1i