# My accepted Java solution. O(n^2 * logn), I think?

• ``````public class Solution
{
public List<List<Integer>> threeSum(int[] num)
{
if (num == null || num.length == 0)
{
return solutionList;    // Return empty list
}

Arrays.sort(num);

// Outer loop iterates through all of the values from left to right, skipping dups
int previousValue = num[0] == 0 ? 1 : 0;
for (int i = 0; i < num.length - 2; ++i)
{
// Progress the outer loop past duplicate values
if (num[i] == previousValue)
{
previousValue = num[i];
continue;
}

// Inner loop iterates from left to right, starting at outer loop index + 1
for (int j = i + 1; j < num.length - 1; ++j)
{
int desiredValue = 0 - (num[i] + num[j]);
if (desiredValue < num[j])
{
break;  // Array is sorted in increasing order; we won't find desired value
}

// Perform array search from j + 1 to num.length for desired value
int keyIndex = Arrays.binarySearch(num, j + 1, num.length, desiredValue);
if (keyIndex >= 0)
{

}

// Progress the inner loop past duplicate values
while (j + 1 < num.length && num[j] == num[j + 1])
{
++j;
}
}

previousValue = num[i];
}

return solutionList;
}
}``````

• Thanks for sharing.

Run your code and got a TLE, and I think your solution can improve a little bit.

As for the outer loop, since a+b+c=0, it means that a should not greater than 0 and c not less than 0, so there should be a turning point from non-positive to non-negative, and only loop i till the turning point should be enough.

So the following can be added, and loop i till <= pivot, can save a bit time when many positive numbers in num array

``````	int pivot = 0;
while (pivot < num.length && num[pivot] < 0) {
pivot++;
}
if(pivot>=num.length-2) pivot = num.length-2;``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.