[LeetCode] Two Sum, 3 Sum, 3 Sum closest and 4 Sum (Java)

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 abc, 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

3 Sum

 3 Sum Closest

4 Sum

 Complexity

This is already discussed in the first part of this post.

  • Hengameh

    The code for 4Sum is O(n^2) as well?

  • dark_knight

    How can the 4Sum be of O(n^2)? You have 2 for loops while iterating over the dict. Doesn’t that make it O(n^3)? Please clarify if I am missing something.

    • decoet

      It’s still O(N^2).

      I think you already know that we use O(N^2) time to create the pairs. And there are at most O(N^2) pairs. In the same time, we have the sum of each pair. We can consider them as O(N^2) elements. Now we are going to calculate 2-sum of these O(N^2) elements.

      We knew that we have a linear algorithm to calculate 2-sum. Now the complexity is O(N^2), since the number of elements is O(N^2).

      So in the end, the complexity of 4-sum is O(N^2).