0015 3Sum

Question

My Solution

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> list = new ArrayList<>();

        for(int i = 0; i < nums.length - 2; i++){
            if(i> 0 && nums[i] == nums[i-1]){
                continue; 
            }
            for(int j = i+1, k = nums.length - 1; j < k; ){
                if(nums[i] + nums[j] + nums[k] == 0){
                    list.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    k--;
                    while((j < k) && (nums[j] == nums[j-1])){
                        j++;
                    }
                    while((j < k) && (nums[k] == nums[k+1])){
                        k--; 
                    }
                }else if(nums[i] + nums[j] + nums[k] > 0){
                    k--;
                }else {
                    j++;
                }
            }
        }
        return list;
    }
}

My Solution 2:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        Set<List<Integer>> map = new HashSet<>();
        int k = nums.length - 1;

        for(int i = 0; i < nums.length - 2; i++){
            int j = i+1;
            k = nums.length - 1;
            while(j < k){
                int sum = nums[j] + nums[k];
                if(sum == -nums[i]){
                    map.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j++;
                    k--;
                }else if(sum < -nums[i]){
                    j++;
                }else {
                    k--;
                }
            }
        }

        return new ArrayList<>(map);
    }
}

Python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        for i, a in enumerate(nums):
            if a > 0:
                break
            if i > 0 and a == nums[i - 1]: # skip the duplicate
                continue
            l, r = i + 1, len(nums) - 1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -= 1
                elif threeSum < 0:
                    l += 1
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while nums[l] == nums[l-1] and l < r:
                        l += 1 # skip the duplicate
        return res