Finding unique triplets adding up to 0

I am working on a problem "3Sum", in which, given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0. I must find all unique triplets in the array which gives the sum of zero.

I wrote my naive implementation which was \$O(n^3)\$ since it was checking for every possible combination:

public List> threeSum(int[] num) {
    List> res=new ArrayList>();

        if(num.length0) break;
            for(int j=i+1;j0 && num[j]>0) break;
                for(int k=j+1;k curr=new ArrayList();
                          curr.add(num[i]);
                          curr.add(num[j]);
                          curr.add(num[k]);
                          res.add(curr);
                      }
                      while(k+1<num.length && num[k]==num[k+1]) k++;
                }
                 while(j+1<num.length && num[j]==num[j+1]) j++;
            }
            while(i+1<num.length && num[i]==num[i+1]) i++;
        }
        return res;

}

However, I am looking for a solution which is better than \$O(n^2)\$. Rather, is there a way I can bring the time complexity of my solution to \$O(n^2)\$ by removing any of the loops?

I don't have a solution better than yours (you can google for java 3Sum O(n^2) to find some examples), but I have some small comments on your code:

While loops

I would remove all the while loops. They make your code harder to read and don't really speed it up (in my tests, they actually slowed it down).

Minor performance improvements

• array access costs time, if you save num[i], etc in local variables, it will slightly speed your code up.

• move quicker checks to the beginning: nj > 0 && ni + nj > 0 instead of ni + nj > 0 && nj > 0 should be quicker, but only marginally so.

Style

• use correct indentation

• in Java, the opening curly bracket commonly goes on the same line

• use curly brackets, even for one-line statements

• use more spaces (for example `while(k+1

StackExchange Code Review Q#68303, answer score: 4