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&lt;List&lt;Integer&gt;&gt; threeSum(int[] num) {
    List&lt;List&lt;Integer&gt;&gt; res=new ArrayList&lt;List&lt;Integer&gt;&gt;();

        if(num.length&lt;3) return res;

       Arrays.sort(num);

        for(int i=0;i&lt;num.length;i++)
        {
         if(num[i]&gt;0) break;
            for(int j=i+1;j&lt;num.length;j++)
            {
                if(num[i]+num[j]&gt;0 &amp;&amp; num[j]&gt;0) break;
                for(int k=j+1;k&lt;num.length;k++)
                {
                    if(num[i]+num[j]+num[k]==0)
                      {
                          List&lt;Integer&gt; curr=new ArrayList&lt;Integer&gt;();
                          curr.add(num[i]);
                          curr.add(num[j]);
                          curr.add(num[k]);
                          res.add(curr);
                      }
                      while(k+1&lt;num.length &amp;&amp; num[k]==num[k+1]) k++;
                }
                 while(j+1&lt;num.length &amp;&amp; num[j]==num[j+1]) j++;
            }
            while(i+1&lt;num.length &amp;&amp; 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 &gt; 0 &amp;&amp; ni + nj &gt; 0 instead of ni + nj &gt; 0 &amp;&amp; nj &gt; 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&lt;num.length &amp;&amp; num[k]==num[k+1]) would be while (k + 1 &lt; num.length &amp;&amp; num[k] == num[k + 1])