3SUM (3SUM)

Description

Given a set $S$ of integers, determine whether there is a subset of $S$ of size 3 that sums to 0.

Related Problems

Generalizations: Real 3SUM

Subproblem: 3SUM', All-Integers 3SUM

Related: All-Integers 3SUM

Parameters

$S$: the set of integers

$n$: the number of integers in the set

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Textbook SortandBinarySearch	-	$O(n^{2} log n)$	$O(n)$	Exact	Deterministic
Textbook SortandTwoSidedTraversal	-	$O(n^{2})$	$O(n)$	Exact	Deterministic
Baran, Demaine, Patrascu	2008	$O(n^{2}/max(w/(log w)$^{2}, (log n)^{2}/(log log n)^{2}))		Exact	Randomized	Time
Baran, Demaine, Patrascu	2008	$O(n^{2}/(w^{2}/(log w)$^{2}))		Exact	Randomized	Time
Baran, Demaine, Patrascu	2008	$O(n^{2}/MB)$		Exact	Randomized	Time
Baran, Demaine, Patrascu	2008	$O(n^{2}*(log M)$^{2}/MB)		Exact	Randomized	Time
Gronlund, Pettie	2014	$O(n^{2}/((log n)$/(log log n))^{2}/{3})		Exact	Deterministic	Time
Gronlund, Pettie	2014	$O(n^{2}*(log log n)$^{2}/(log n))		Exact	Randomized	Time
Freund	2017	$O(n^{2}*(log log n)$/(log n))		Exact	Deterministic	Time
Chan	2018	$O(n^{2}*(log log n)$^{$O({1})$}/(log n)^{2})		Exact	Deterministic	Time

Reductions TO Problem

Problem	Implication	Year	Citation	Reduction
3SUM'	if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$ then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$	1995	https://doi.org/10.1016/0925-7721(95)00022-2	link
3 Points on Line	if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$ then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$	1995	https://doi.org/10.1016/0925-7721(95)00022-2	link
Local Alignment	if: to-time $N^{2-\delta-\epsilon} for two strings of size $n$ and alphabet of size $n^{1-\delta}$ for some $\espilon > {0}$,$\delta \in ({0},{1})$ then: from-time: $n^{2-\epsilon'}$ for some $\epsilon' > {0}$	2014	https://link.springer.com/chapter/10.1007/978-3-662-43948-7_4	link
All-Integers 3SUM	if: to-time: $T(n)$ then: from-time: $O(T(n))$			link

Reductions FROM Problem

Problem	Implication	Year	Citation	Reduction
3SUM'	if: to-time $N^{2-\epsilon}$ for some $\epsilon > {0}$ then: from-time: $N^{2-\epsilon'}$ for some $\epsilon' > {0}$	1995	https://doi.org/10.1016/0925-7721(95)00022-2	link
All-Integers 3SUM	if: to-time: $O(n^{2-\epsilon})$ for some $\epsilon > {0}$ then: from-time: $O(n^{1.5} + n^{2-\epsilon / 2})$	2018	https://dl.acm.org/doi/pdf/10.1145/3186893, Theorem 8.1	link

References/Citation

https://link.springer.com/article/10.1007/s00453-007-9036-3