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.
The solution set must not contain duplicate triplets.
This problem is commonly known as three sum problem.
Input: = [-1, 0, 1, 2, -1, -4], Output: [ [-1, 0, 1], [-1, -1, 2] ]
This problem is commonly asked in Amazon and Google interviews.
Three Sum problem : thought process
Before going into the details of find three numbers with a given sum, do you know how to find two numbers with a given sum s? The idea is simple, we keep a map of all the numbers in we already seen, if see a number a[i], we see in the map if S-a[i] is present or not. If yes, then we found the pair, if not, we put a[i] and move forward.
This solution has linear time complexity i.e O(n) with a space complexity of O(n) as well. There is a way to avoid space complexity by sorting the input array first and using two pointer approach.
Details of 2 sum problem, you can read here: 2 Sum problem: Find pair with given sum in array
Can we use our understanding of the two-sum problem to solve this three-sum problem?
Hint 1:
What happens if we take one number from the array and say that this number will be one of the three numbers which add up to zero? What happens to our problem statement now?
Hint 2:
If you have decided that A[0] will be part of three numbers which add up to zero, all we need is two find out two numbers from index 1..len-1 which add up to O – A[0]. What does that mean? It looks like a 2-sum problem, doesn’t it?

Show me the implementation of three sum problem
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); //O(n log n) Arrays.sort(nums); for(int i=0; i<nums.length; i++){ if (i > 0 && nums[i] == nums[i - 1]) { continue; } if(nums[i] > 0) continue; int j = i+1; int k = nums .length -1; int target = 0-nums[i]; /* Below code is exactly the same to find two numbers with a given sum using two pointers */ while(j<k){ if(nums[j] + nums[k] == target ){ /* If find j and k, such that element at index i, j and K add to zero, put them in result */ ArrayList<Integer> triplet = new ArrayList<Integer>( Arrays.asList(nums[i], nums[j], nums[k])); j++; k--; while (j < k && nums[j] == nums[j - 1]) j++; // skip same result while (j < k && nums[k] == nums[k + 1]) k--; // skip same result //since we want only unique triplets, using set result.add(triplet); } else if(nums[j] + nums[k] > target){ k--; } else{ j++; } } } return result; } }
If you do not come up with the idea of moving i, j and k to get unique triplets, it is OK. You can always use HashSet to filter out duplicates and then copy the HashSet to the result list. It will take more time but will give the correct result.
if(uniqueSet.add(triplet)){ result.add(triplet); }
The time complexity of the solution is O(n2) plus the complexity of sorting algorithm (never forget that to mention!!). However, sorting complexity is O(nlogn), hence the overall complexity is dominated by the quadratic expression.
Can you solve the following problems on the leetcode?
1. 3SUM
2. 3Sum Closest
3. Four sum problem.