# Simple O(n^2) two pointers Java solution

• Runtime = O(n^2); Space = O(1)

``````public List<List<Integer>> threeSum(int[] A) {
List<List<Integer>>res = new ArrayList<List<Integer>>();
if (A == null || A.length == 0)
return res;
Arrays.sort(A);
for (int i = 0; i < A.length; i++) {
if (i - 1 >= 0 && A[i] == A[i - 1]) continue;// Skip equal elements to avoid duplicates

int left = i + 1, right = A.length - 1;
while (left < right) {// Two Pointers
int sum = A[i] + A[left] + A[right];
if (sum == 0) {
while (left + 1 < right && A[left] == A[left+1])// Skip equal elements to avoid duplicates
left++;
while (right -1 > left && A[right] == A[right-1])// Skip equal elements to avoid duplicates
right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return res;
}``````

• Fancy. You literally reduce the time complexity from O(n^3) to O(n^2).

Here are some comments tho, we might need to add the if statement to check whether the list length is greater than 2 or not, it not then return an empty list directly.

``````    List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums.length <=2) return result;
//its length needs to be checked before the array get sorted
Arrays.sort(nums);
``````

• Thanks for the comment, Bobo. If the length of nums equals 2, start will be 1, and end will be 1, doesn't satisfy start < end, then the loop will exit correspondingly.

• You are absolutely right!

• for empty array , even after returning empty list why it is giving compile error
expected input: []
expected output: []

• Hi, abhishek72, maybe the returned value type should be List<List<Integer>>.

• I tried your code , but always got this TLE case, [7,-1,14,-12,-8,7,2,-15,8,8,-8,-14,-4,-5,7,9,11,-4,-15,-6,1,-14,4,3,10,-5,2,1,6,11,2,-2,-5,-7,-6,2,-15,11,-6,8,-4,2,1,-1,4,-6,-15,1,5,-15,10,14,9,-8,-6,4,-6,11,12,-15,7,-1,-9,9,-1,0,-4,-1,-12,-2,14,-9,7,0,-3,-4,1,-2,12,14,-10,0,5,14,-1,14,3,8,10,-8,8,-5,-2,6,-11,12,13,-7,-12,8,6,-13,14,-2,-5,-11,1,3,-6],anybody can explain me this? I also got this TLE case in my own O(n^2) code.

• Hi, enming, thanks for the comment, it can work correctly now.

• Nice code, for O(n^2)

• This is wrong, think about[-2,0,2,1,1,2]

• Brilliant code!

I guess there might be minor improvement you can make. for the cases where sum < 0 and sum >0, you may also jump over the duplicate elements and therefore save some operations.i.e change

``````else if (sum < 0) {
left++;
} else {
right--;
}
``````

to

``````else if (sum < 0) {
left++;
while (left < right && A[left] == A[left-1])// Skip equal elements to avoid duplicates
left++;
} else {
right--;
while (right > left && A[right] == A[right+1])// Skip equal elements to avoid duplicates
right--;``````

• @enming in the for loop, i should be "i < nums.length - 2", not "i < nums.length"......I think it's a typo here = =

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