Is it possible to solve 3SUM in $O(n^2)$ time?
A $O(n^2)$ algorithm (with $O(1)$ space) is as follows:


Sort $A$, $B$, and $C$ individually in $O(n \log n)$.
For each $a \in A$:


Search a pair of $b \in B$ and $c \in C$ such that $b + c = k - a$. This can be done in $O(n)$ by traversing $B$ from the smallest to the largest and $C$ from the largest to the smallest. (Tip: Comparing $b + c$ with $k-a$ each time.)