In LeetCode, there are a set of problems to find the sum of several integers from an array to be a target value.
Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
3 Sum Closest:
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
4 Sum
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
- Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
- The solution set must not contain duplicate quadruplets.
Analysis
Brute force
If we use brute force to solve Two Sum, it will cost us $O(n^2)$ to find the answer. Similarly, the complexity of solving 3 Sum using brute force is $O(n^3)$, which is not good for these problems.
Sorting
We can sort the array to make it easier. For Two Sum, if the array is sorted, we can use two pointers pointing to the head and the end. If the sum is smaller than target, we can move the first pointer right. If the sum is larger than target, we can move the second pointer left. We will continue doing this until we find the target or the position of first pointer is larger than the second pointer. We can also use this in 3 Sum. We can use each entry as a candidate. For example, we now searching 2 other elements in the array that makes their sum equals to target – num[i]. We can just check the entries from i + 1 to num.length – 1, with the method mentioned above.
3 Sum Closest can also be solved like this. We just check every candidate for the most closest one.
The complexity of this method is better than brute force method. Sorting the array costs $O(nlogn)$. So, for Two Sum, it costs $O(nlogn)$. For 3 Sum, it costs $O(nlogn)$ + $O(n^2)$ = $O(n^2)$. For 4 sum, it costs $O(n^3)$.
HashMap
We can use HashMap to improve this algorithm. For example, it can improve Two Sum from $O(nlogn)$ to $O(n)$. That is, saving every number in the HashMap as well as its position. And then we can go through the array and check for the existence number target – i in $O(1)$. So we only need $O(n)$. Similarly, with HashMap we can solve 3 Sum in $O(n^2)$ and 4 Sum in $O(n^2)$.
Duplication
In some problems we are are required to output non-duplicate result. We can use HashSet to achieve this.
Code
2 Sum
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class Solution { public int[] twoSum(int[] numbers, int target) { HashMap<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < numbers.length; i++) { map.put(target - numbers[i], i); } for (int i = 0; i < numbers.length; i++) { if (map.containsKey(numbers[i])) { if (map.get(numbers[i]) != i) { return new int[]{i + 1, map.get(numbers[i]) + 1}; } } } return new int[2]; } } |
3 Sum
|
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 26 27 28 29 |
public class Solution { public List<List<Integer>> threeSum(int[] num) { Arrays.sort(num); LinkedList<List<Integer>> ret = new LinkedList<>(); HashSet<List<Integer>> set = new HashSet<>(); for (int i = 0; i < num.length - 2; i++) { int start = i + 1; int end = num.length - 1; while (start < end) { if (num[i] + num[start] + num[end] == 0) { LinkedList<Integer> oneResult = new LinkedList<>(); oneResult.add(num[i]); oneResult.add(num[start]); oneResult.add(num[end]); set.add(oneResult); start++; end--; } else { if (num[i] + num[start] + num[end] < 0) start++; else end--; } } } ret.addAll(set); return ret; } } |
3 Sum Closest
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public class Solution { public int threeSumClosest(int[] num, int target) { int closest = num[0] + num[1] + num[2]; int diff = Math.abs(closest - target); Arrays.sort(num); for (int i = 0; i < num.length - 2; i++) { int start = i + 1; int end = num.length - 1; while (start < end) { int sum = num[i] + num[start] + num[end]; int newDiff = Math.abs(sum - target); if (newDiff < diff) { diff = newDiff; closest = sum; } if (sum < target) start++; else end--; } } return closest; } } |
4 Sum
|
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
public class Solution { public List<List<Integer>> fourSum(int[] num, int target) { //Create the dictionary. HashMap<Integer, ArrayList<ArrayList<Integer>>> dict = new HashMap<>(); for (int i = 0; i < num.length - 1; i++) { for (int j = i + 1; j < num.length; j++) { int sum = num[i] + num[j]; ArrayList<Integer> pair = new ArrayList<>(2); pair.add(i); pair.add(j); if (!dict.containsKey(sum)) { ArrayList<ArrayList<Integer>> value = new ArrayList<>(); value.add(pair); dict.put(sum, value); } else { ArrayList<ArrayList<Integer>> value = dict.get(sum); value.add(pair); } } } //Use HashSet to prevent duplicate result. HashSet<ArrayList<Integer>> set = new HashSet<>(); for (Integer sum : dict.keySet()) { ArrayList<ArrayList<Integer>> sumPair = dict.get(sum); if (dict.containsKey(target - sum)) { if (target - sum == sum && sumPair.size() == 1) continue; ArrayList<ArrayList<Integer>> pairs = dict.get(target - sum); for (ArrayList<Integer> pair1 : sumPair) { for (ArrayList<Integer> pair2 : pairs) { //Make sure it is not the same pair. if (pair1 == pair2) continue; //Make sure there is no same element in two pairs. if (pair1.contains(pair2.get(0)) || pair1.contains(pair2.get(1))) continue; ArrayList<Integer> tmpResult = new ArrayList<>(4); tmpResult.add(num[pair1.get(0)]); tmpResult.add(num[pair1.get(1)]); tmpResult.add(num[pair2.get(0)]); tmpResult.add(num[pair2.get(1)]); //Sort the list and add it into the set. Collections.sort(tmpResult); set.add(tmpResult); } } } } List<List<Integer>> ret = new LinkedList<>(); ret.addAll(set); return ret; } } |
Complexity
This is already discussed in the first part of this post.