15. 3Sum

Description

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Constraints

• 0 <= nums.length <= 3000

• -105 <= nums[i] <= 105

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: nums = [-1, 0, 1, 2, -1, -4]

Output: [[-1, -1, 2], [-1, 0, 1]]

Example 2

Input: nums = [0]

Output: []

Example 3

Input: nums = []

Output: []

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> resultList = new HashSet();
        if(nums == null || nums.length < 3) {
            new ArrayList(resultList);
        }
        
        helper(nums, resultList, new LinkedList<Integer>(), 0, 0);
        
        return new ArrayList(resultList);
    }
    
    private void helper(int[] nums,
                        Set<List<Integer>> resultList,
                        LinkedList<Integer> currList,
                        int start,
                        int sum) {
        if(currList.size() == 3) {
            if(sum == 0) {
                List<Integer> tmpList = new ArrayList(currList);
                Collections.sort(tmpList);
                resultList.add(tmpList);
            }
            return;
        }
        for(int i = start; i < nums.length; i++) {
            currList.add(nums[i]);
            helper(nums, resultList, currList, i+1, sum+nums[i]);
            currList.removeLast();
        }
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        int n = nums.length;
        Arrays.sort(nums);
        for(int i = 0; i < n; i++) {
            int val = nums[i];
            int l = i+1;
            int r = n-1;
            while(l < r) {
                int sum = val + nums[l] + nums[r];
                if(sum == 0) {
                    res.add(Arrays.asList(val, nums[l++], nums[r--]));
                }
                else if(sum < 0) l++;
                else if(sum > 0) r--;
            }
        }
        return new ArrayList<>(res);
    }
}

Solution 3

/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i-1] == nums[i]) continue;
            int l = i+1, r = nums.length-1;
            while(l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if(sum < 0) l++;
                else if(sum > 0) r--;
                else {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    while(l < r && nums[l] == nums[l+1]) l++;
                    while(l < r && nums[r] == nums[r-1]) r--;
                    l++;
                    r--;
                }
            }
        }
        return res;
    }
}

Follow up