Given a set of both positive and negative numbers, what is a time optimal approach to find the two numbers whose sum, plus a third number is zero

Question

Coming from an engineering background I want to solve this question.

Question:

Given a set of positive, and negative numbers, how do I time optimally find two numbers whose sum is the mathematical negative of a third number?

Breakdown of question:

I have isolated two keywords, dynamic programming and number partitioning (number theory) and a reference to this hard problem

I believe the solution might require a use of a 2d, or 3d indexed structure whose indices go from 0 -> minimum cubic value from the max value in the set, and use that indexed structure to find relevant information

https://www.geeksforgeeks.org/partition-a-set-into-two-subsets-such-that-the-difference-of-subset-sums-is-minimum/

Determine if a set has three integers that add to zero, in some time, that has been sub-optimally determined to be N squared, for all possible combinations of pairs of numbers to be selected, to be compared to a third.

I reduced it to read as such.

1)Find all two numbers in a sub quadradic computation time.

2)Find all the corresponding third number that cancels or doubles the value

But how... so I divided the problem further... Find a way to represent numbers graphically that adds up and came up with some approaches.

1. Use the set but create a copy, like in a computer so that it will operate like a shift register from start to finish, while forgetting duplicates
2. Remains the question of storage, what computing data structure would accomplish remembering what I have, and that is where I stopped
3. I considered using a space possibly inefficient 3D representation of the numbers like an Octree to solve this, because I can sparsely specify data points to be stored based on criteria x,y,z, but do I need to have a large space allocated for this structure that for my number set based on my set's max number's number of digits for all numbers
4. How can I exploit mathematical laws of numbers 0-9 to optimize determination of the two values to pick from the array, some how, like a linkage or another set of numbers
5. How do I process the numbers faster, as this is already solved in computer science, by means of linear time sorting algorithms like Radix Sorting, with a Binary Search algorithm.

*) Finding the last number is a matter of either adding to double the sum, or diving by a 1st power 2 to get (shift right in computer arithmetic) to equal the average of the two numbers added together

Do any of these approaches solve this problem of finding a number whose sum is 0, whose absoluteValue(a+b) equals c, or avg(abs(a+b)) = c >> 2;

Any suggestions to help in moving me forward would be tremendously appreciated.

Thank You.

Answer 1

This is a famous open problem in algorithms, with links to finding triangles in graphs, and other problems.

There are some mildly subquadratic solutions known but that’s about it. You can ask the same for real numbers, only positive integers, rationals, other group elements.

The paper "Subquadratic Algorithms for 3SUM", by Ilya Baran, Erik D. Demaine, Mihai Patrascu has the following complexity for the

3SUM problem: given a list $L$ of $n$ integers if there are $x,y,z \in L$ such that $x+y=z.$

Recently, a paper "Threesomes, Degenerates, and Love Triangles" by Grondlund and Pettie has proved that "the decision tree complexity of 3SUM is $O(n^{3/2}\sqrt{\log n})$, and that there is a randomized 3SUM algorithm running in $O(n^2(\log \log n)^2/\log n)$ time, and a deterministic algorithm running in $O(n^2(\log \log n)^{5/3}/(\log n)^{2/3})$ time.

These results refute the strongest version of the 3SUM conjecture, namely that its decision tree (and algorithmic) complexity is $Ω(n^2)$."

See this second paper here.

See the question and answer in TCS stackexchange here for more.