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


  • 0
    M
    public class Solution 
    {
        public List<List<Integer>> threeSum(int[] num) 
        {
            List<List<Integer>> solutionList = new LinkedList<List<Integer>>();
            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)
                    {
                        List<Integer> solutionSet = new LinkedList<Integer>();
                        solutionSet.add(num[i]);
                        solutionSet.add(num[j]);
                        solutionSet.add(num[keyIndex]);
                        
                        solutionList.add(solutionSet);
                    }
                    
                    // Progress the inner loop past duplicate values
                    while (j + 1 < num.length && num[j] == num[j + 1])
                    {
                        ++j;
                    }
                }
                
                previousValue = num[i];
            }
            
            return solutionList;
        }
    }

  • 0

    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;

Log in to reply
 

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