3Sum

Question: 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.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

You may view the full question here.

Approach 1: Was simply trying to use the 2 sum approach and extending it. But that seems to be an awful idea, as it keeps returning Time Limit Exception. Here is the code —

//Approach 1
//Runtime: Time Limit Exception
//Memory usage: N/A
class Solution {
    HashMap<Integer, HashSet<Integer>> map = new HashMap();
    public List<List<Integer>> threeSum(int[] nums) {
        map = new HashMap();
        List<List<Integer>> result = new ArrayList<>();
        for(int i = 0; i<nums.length; i++){
            int num = nums[i];
            List<List<Integer>> listOfList = twoSum(nums, i, -1*num);
            for(List<Integer> list : listOfList){
                list.add(num);
                result = addOnlyUnique(result, list);
            }            
        }
        return result;
    }
    
    private List<List<Integer>> addOnlyUnique(List<List<Integer>> result, List<Integer> list){
        Collections.sort(list);
        boolean unique = true;
        for(List<Integer> l : result){
            boolean match = true;
            for(int i = 0; i<3; i++){
                if(l.get(i)!=list.get(i)){
                    match = false;
                    break;
                }
            }
            if(match){
                return result;
            }
        }
        result.add(list);
        return result;
    }
    
    private List<List<Integer>> twoSum(int[] nums, int except, int target) {
        List<List<Integer>> result = new ArrayList();
        for(int i = 0; i<nums.length; i++){
            if(i!=except){
                int a = nums[i];
                int b = target - a;
                if(map.containsKey(b)){
                    HashSet<Integer> indices = map.get(b);
                    for(Integer ind : indices){
                        if(ind!=i && ind!=except){
                            List<Integer> list = new ArrayList();
                            list.add(a);
                            list.add(b);
                            result.add(list);
                        }
                    }
                } else {
                    if(map.containsKey(a)){
                        HashSet<Integer> set = map.get(a);
                        if(!set.contains(i)){
                            set.add(i);
                            map.put(a, set);
                        }
                    } else {
                        HashSet<Integer> set = new HashSet();
                        set.add(i);
                        map.put(a, set);
                    }                    
                }
            }
        }
        return result;
    }
}

A long way to go. You might want to check this next post for a better implementation.

Find more posts here.

Cheers & Chao!