15. 3Sum

Posted on | Edited on | Views:

LeetCode

Approach: Two Pointers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    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||i>0&&nums[i]!=nums[i-1]){
                int l=i+1,h=nums.length-1,sum=0-nums[i];
                while(l<h){
                    if(nums[l]+nums[h]==sum){
                        res.add(Arrays.asList(nums[i],nums[l],nums[h]));
                        while(l<h&&nums[l]==nums[l+1]) l++;
                        while(l<h&&nums[h]==nums[h-1]) h--;
                        l++;
                        h--;
                    }else if(nums[l]+nums[h]<sum){ 
                        l++;
                    }else {
                        h--;
                    }
                }
            }
        }
        return res;
    }
}

0%