For example, nlog(n)? since we have sort the array, it seems like we might able to do better.
Any solution which is better than O(n^2) exists?

No, you can't. If you're interested, here is a paper that proves a lower bound of Ω(n^ceil(k/2)) for the kSUM problem (deciding whether k numbers out of n sums to 0) where ceil is the ceiling function. Here k=3, so you cannot do better than Ω(n^2).
Fun fact, there exist better quantum algorithms. The quantum complexity of kSUM is Θ(n^(k/(k+1)) which is sublinear! How cool is that? (Here is the paper describing the algorithm, and here the proof of optimality)

@loick those papers are deep.... thanks
I have a doubt though: if the bound is Ω(n^ceil(k/2)), then for 4sum problem, the theoretically best solution should be O(n^2), but I cannot see anyone can solve that in O(n^2) time. What is wrong here?
Any one?


@gpf828 Yeah.. I understand the lower bound part. So it is theoretically possible to find a O(n^2) solution?

I believe there is O(nlogn) solution.
The basic idea is this:
 Sort the array
 With N numbers you can generate N^3 3tuples
 If the array is sorted sum(0,1,2) <= sum(len/21,len/2,len/2+1) <= sum(len3, len2, len1). Note that the index in the inequality may be out of bounds, but it is only to provide the idea.
 You can now imagine a cubic search space. And if you considered the center of the cube and compared with the diagonal ends, it can be seen that the problem can be reduced to 7/8 in each step.
4.1 for eg: If sum of cube mid point is greater than target sum. it can be noted that the cube with diagonal (mid,mid,mid) > (len1, len1, len1) can be dropped from search space. Note that the value uniqueness constraint in the 3tuple should be additionally maintained.  It is a modification of binary search but in a 3 dimensional space.
 Analysis: sort > nlogn, search = 3/(log(8/7,2)/log(2)) * log(N, 2). Which implies a nlogn + ~5 logn solution. O(nlogn)


@chidong This implementation timed out (but solutions were correct until it timed out). I am possibly missing something. From what I am reading, I assume folks have gotten an accept with n^2. Hope this helps.
public Solution { private static class Tuple3 implements Comparable<Tuple3> { // Implements a simple Tuple of three elements and is comparable. // Skipping implementation for brevity } // Time complexity: O(nlogn) (nlogn for sort and O(logn) for search) public static List<List<Integer>> threeSum(int[] nums) { // Sort the input Arrays.sort(nums); int len = nums.length; Set<Tuple3> sols = new TreeSet<>(); // Start with the ends of the diagonal of the cube Tuple3 start = new Tuple3(0, 1, 2); Tuple3 end = new Tuple3(len3, len2, len1); threeSum(nums, start, end, sols); // Transform to list for returning the expected structure List<List<Integer>> finalSols = new ArrayList<>(); for (Tuple3 sol : sols) { finalSols.add(sol.toList()); } return finalSols; } private static void threeSum(int[] nums, Tuple3 start, Tuple3 end, Set<Tuple3> sols) { // Termination (when start > end) if (start.getA() > end.getA()  start.getB() > end.getB()  start.getC() > end.getC()) { return; } // Centroid of the cube Tuple3 mid = centroid(start, end); // Another termination condition where the cube is a unit cube. // Handle specially if (start.equals(mid)) { unitCube(start, end, nums, sols); return; } int sa = start.getA(); int sb = start.getB(); int sc = start.getC(); int ma = mid.getA(); int mb = mid.getB(); int mc = mid.getC(); int ea = end.getA(); int eb = end.getB(); int ec = end.getC(); // Sum of centroid int sum = nums[ma] + nums[mb] + nums[mc]; // Found a solution if (sum == 0) { updateSol(ma, mb, mc, nums, sols); } // If equal = 0 explore all 8 cubes. Else depending on whether sum is greater // than or less than 0, we can skip one cube out of 8. The recursive calls take // new diagonal end points of the sub cubes. if (sum <= 0) { threeSum(nums, new Tuple3(ma, mb, mc), new Tuple3(ea, eb, ec), sols); } if (sum >= 0) { threeSum(nums, new Tuple3(sa, sb, sc), new Tuple3(ma1, mb1, mc1), sols); } threeSum(nums, new Tuple3(ma, sb, sc), new Tuple3(ea, mb1, mc1), sols); threeSum(nums, new Tuple3(sa, mb, sc), new Tuple3(ma1, eb, mc1), sols); threeSum(nums, new Tuple3(ma, mb, sc), new Tuple3(ea, eb, mc1), sols); threeSum(nums, new Tuple3(ma, sb, mc), new Tuple3(ea, mb1, ec), sols); threeSum(nums, new Tuple3(sa, mb, mc), new Tuple3(ma1, eb, ec), sols); threeSum(nums, new Tuple3(sa, sb, mc), new Tuple3(ma1, mb1, ec), sols); } // Note that this function runs only for the case where distance(start, end) <= 1 private static void unitCube(Tuple3 start, Tuple3 end, int[] nums, Set<Tuple3> sols) { for (int a = start.getA(); a <= end.getA(); ++a) { for (int b = start.getB(); b <= end.getB(); ++b) { for (int c = start.getC(); c <= end.getC(); ++c) { updateSol(a, b, c, nums, sols); } } } } private static void updateSol(int a, int b, int c, int[] nums, Set<Tuple3> sols) { Set<Integer> indices = new HashSet<>(); indices.add(a); indices.add(b); indices.add(c); if (indices.size() == 3) { if (nums[a] + nums[b] + nums[c] == 0) { sols.add(new Tuple3(nums[a], nums[b], nums[c])); } } } private static Tuple3 centroid(Tuple3 a, Tuple3 b) { int mida = (a.getA() + b.getA()) / 2; int midb = (a.getB() + b.getB()) / 2; int midc = (a.getC() + b.getC()) / 2; return new Tuple3(mida, midb, midc); } }

Yes O(n^2/(log n/ log log n)^2/3) according to wiki (https://en.wikipedia.org/wiki/3SUM)