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

  • 2
    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;
            for(int i=0;i<nums.length;i++){
                int low = i+1;
                int high = nums.length -1;
                        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--;
                    } 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

    why you use this three while loops ? can plzz explain

  • 0

    Added explanation.

Log in to reply

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