Three sum

In computational complexity theory, the 3SUM problem asks if a given set of \(n\) real numbers contains three elements that sum to zero. A generalized version, k-SUM, asks the same question on k numbers. 3SUM can be easily solved in \(\bigo{n^2}\) time, \({\bigomega{n^{\lceil k/2\rceil }}}\) lower bounds are known in some specialized models of computation (Erickson 1999).

(“3SUM” 2022)

Three sum is a Technical interview question and a variant of the Subset sum problem.

Quadratic solution (\(\bigo{n^2}\))

3sum solution in Python

Bibliography