Clean Java O(n^2) solution using two pointers


  • 2
    M
    public class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if(nums==null || nums.length<3) return result;
            Arrays.sort(nums);
            for(int i=0;i<nums.length;i++){
                int low = i+1;
                int high = nums.length -1;
                while(low<high){
                    if(nums[i]+nums[low]+nums[high]==0){
                        result.add(Arrays.asList(nums[i], nums[low], nums[high]));
                        while(i+1<nums.length && nums[i+1]==nums[i]) i++;
                        while(low+1<nums.length && nums[low]==nums[low+1]) low++;
                        while(high-1>=0 && nums[high]==nums[high-1]) high--;
                        low++;
                        high--;
                    } else if(nums[i]+nums[low]+nums[high]>0) high--;
                    else low++;
                }
            }
            return result;
        }
    }
    

    The inner three while loops ensure that if there are duplicate numbers, only one of the duplicate number is added to the solution.

    Suppose the array is [2, 2, 5, 9, -7]

    When i = 0, low = 2, high = 4, the sum would be 0 and hence the solution would be added to the list.
    Now if we don't have these while loops and we let the for loop increment i to 1, we will once again get the same solution since 2 appears twice in the array.


  • 0
    M

    why you use this three while loops ? can plzz explain


  • 0
    M

    Added explanation.


Log in to reply
 

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