[Leetcode] TwoSum, ThreeSum, FourSum and KSum

Two Sum:

Given an array of integers A, and a target t,  find two numbers in A such that their sum equals t. Return the index of two numbers, in increasing order. You may assume that each input would have exactly one solution.
Example:

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Algorithm:

1. Brute Force: 
Find all pairs of numbers and calculate their sum, if it equals the target return their index in increasing order. Running time = O(n^2).

2. Sort + Double Pointer
First, sort the array in O(n*Log(n)) time. Then use two pointers p and q, p scans from left to right, and q scans from right to left.
While(p < q)
       if(p+q = target) return p and q
       else if(p+q < target) p++
       else q++
End
Therefore, the running time = O(n*Log(n))

3. Hash Map:
We can do even better, by using hash map. First we create a hash map, where
                                    [key, value] = [target - A[i], i].
This requires O(n). Then, we iterate the array. If A[j] contains in map, which means A[j] = target - A[i], we return i and j. This solution has a running time O(n), and its space complicity is O(n). We used O(n) space to reduce the running time.
Note, one number may be used twice, therefore, we need to check j != map.get(A[j])

Three Sum:

Find three numbers, instead of two, where a+b+c = target, return their index in increasing order. 

Algorithm:

1. Reduce to Two Sum 

Sort Array A

For each  i = 0 to A.length-1

        (j,k) = twoSum(A.rest, target - A[i]) 

        If j,k are valid solution 

             return i,j,k

        End

End

Running Time = O(n^2).

2. Hash Map

Create a hash map where [key, value] = [target - A[i], i]

For j = 0 to A.length -2

   For k = j+1 to A.length-1

        if(A[j] + A[k] is in map AND its index > k)

               return j,k and i

End

Running time = O(n^2). 

Here, index > j ensures no duplicate solutions, each newly found solution is a new solution. If For example, A = [1,2,3,4,5] and target = 9. When j = 1, and k =2, we can find a solution index = [1,2,3]. However, if we don't require i > k, we will get this solution again, when j =2 and k =3. 

Duplicate elements. 

How about A has duplicate elements, e.g A = [-1,-1,0,1] and target = 0. I should have only one solution [-1,-1,0]. But using above algorithm, we will get two results. 

Observation :

     for fixed j, once we find a k > i and i > k that A[j]+A[k] + A[i] = target, we will not find any new solution with j and this k. 

Therefore, when we enter the if block, we can safely skip all other same elements equal to A[k]. See more details in code below. 

Four Sum

We can reduce the four sum problem to a three sum problem, then to a two sum problem. 

For i = 0 to A.length-4

   For j = 0 to A.length-3

        find twoSum in A[j+1 to End] and target = -(A[i] + A[j])

   EndFor

EndFor

Also, we need to skip all duplicate solutions. Running time = O(n^3). 

Three Sum Closest

Using hash map is hard to solve this problem, instead we can reduce it to two closet sum problem. 

For each i = 0 to A.length-1

   find a two sum in A[i+1 to end] which is closest to target - A[i]

End