3Sum Two Pointers

Medium

Python

def three_sum(nums):
    nums.sort(); res=[]
    for i in range(len(nums)-2):
        if i>0 and nums[i]==nums[i-1]: continue
        l,r=i+1,len(nums)-1
        while l<r:
            s=nums[i]+nums[l]+nums[r]
            if s==0: res.append([nums[i],nums[l],nums[r]]); l+=1; r-=1
            elif s<0: l+=1
            else: r-=1
    return res

Java

public List<List<Integer>> threeSum(int[] nums){
    Arrays.sort(nums); List<List<Integer>> res=new ArrayList<>();
    for(int i=0;i<nums.length-2;i++){
        if(i>0&&nums[i]==nums[i-1]) continue;
        int l=i+1,r=nums.length-1;
        while(l<r){
            int s=nums[i]+nums[l]+nums[r];
            if(s==0){res.add(Arrays.asList(nums[i],nums[l],nums[r]));l++;r--;}
            else if(s<0) l++; else r--;
        }
    } return res;
}

Key Insight

Java generic types verbose. Two-pointer logic identical.

Python → Java Differences

Python list vs List<List<Integer>>
append vs add(Arrays.asList())
Two-pointer identical

Python

def three_sum(nums):
    nums.sort(); res=[]
    for i in range(len(nums)-2):
        if i>0 and nums[i]==nums[i-1]: continue
        l,r=i+1,len(nums)-1
        while l<r:
            s=nums[i]+nums[l]+nums[r]
            if s==0: res.append([nums[i],nums[l],nums[r]]); l+=1; r-=1
            elif s<0: l+=1
            else: r-=1
    return res

Java

public List<List<Integer>> threeSum(int[] nums){
    Arrays.sort(nums); List<List<Integer>> res=new ArrayList<>();
    for(int i=0;i<nums.length-2;i++){
        if(i>0&&nums[i]==nums[i-1]) continue;
        int l=i+1,r=nums.length-1;
        while(l<r){
            int s=nums[i]+nums[l]+nums[r];
            if(s==0){res.add(Arrays.asList(nums[i],nums[l],nums[r]));l++;r--;}
            else if(s<0) l++; else r--;
        }
    } return res;
}

Algorithm Steps

1. Sort
2. Fix first
3. Two-pointer for rest

← Previous All Two Pointers Next →