Simple O(n^2) two pointers Java solution


  • 28

    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) { 
    				res.add(Arrays.asList(A[i], A[left], A[right]));
    				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;
    }

  • 1
    B

    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);
    

  • 0

    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.


  • 0
    B

    You are absolutely right!


  • 0
    A

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


  • 0

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


  • 0
    E

    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.


  • 0
    S

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


  • 0
    Z

    Nice code, for O(n^2)


  • 0
    C

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


  • 0
    S

    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--;

  • 0

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


Log in to reply
 

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