Leetcode 18 - 4Sum

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.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

X. O(N^3)
https://discuss.leetcode.com/topic/12368/clean-accepted-java-o-n-3-solution-based-on-3sum
http://www.programcreek.com/2013/02/leetcode-4sum-java/

A typical k-sum problem. Time is N to the power of (k-1).

    public List<List<Integer>> fourSum(int[] num, int target) {
        ArrayList<List<Integer>> ans = new ArrayList<>();
        if(num.length<4)return ans;
        Arrays.sort(num);
        for(int i=0; i<num.length-3; i++){
            if(i>0&&num[i]==num[i-1])continue;//\\
            for(int j=i+1; j<num.length-2; j++){
                if(j>i+1&&num[j]==num[j-1])continue;//\\
                int low=j+1, high=num.length-1;
                while(low<high){
                    int sum=num[i]+num[j]+num[low]+num[high];
                    if(sum==target){
                        ans.add(Arrays.asList(num[i], num[j], num[low], num[high]));
                        while(low<high&&num[low]==num[low+1])low++;
                        while(low<high&&num[high]==num[high-1])high--;
                        low++;
                        high--;
                    }
                    else if(sum<target)low++;
                    else high--;
                }
            }
        }
        return ans;
    }

http://buttercola.blogspot.com/2014/07/leetcode-4sum.html
Look the code carefully then you will find a bug. Let's see the results first. According to the OJ, it failed the test:

Input:	[1,-2,-5,-4,-3,3,3,5], -11
Output:	[]
Expected:	[[-5,-4,-3,1]]

But why? According to the code above, we sorted the array first, so it becomes [-5, -4, -3, -2, 1, 3, 3, 5], and the target is -11.  
Now you might find the problem. In Line 11, it checks 

?

1	if (num[i] > target) break;

However, when the target is a negative number , this condition no longer stands, because as is shown in the data input above, even if num[i] is greater than the target, it is possible that the numbers on the right hand side of num[i] are negative number. So we still have to check. 
For the case when the target is equal or greater than 0, this condition stands anyway, because the num[i] and its later on numbers must be positive numbers. Consequently, after we removed the line 12 and 16, the code becomes correct, which is as shown below:

    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {

        final int length = num.length;

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

         

        if (length < 4) return result;

         

        // Sort the array

        Arrays.sort(num);

         

        for (int i = 0; i < length - 3; i++) {

            if (num[i] > target) break; //remove

            //if (i == 0 || num[i] > num[i - 1]) {

                for (int j = i + 1; j < length - 2; j++) {

                    //if (j == i + 1 || num[j] > num[j - 1]) {

                        if ((num[i] + num[j]) > target) break; // remove

                        int start = j + 1;

                        int end = length - 1;

                        int newTarget = target - (num[i] + num[j]);

                        while (start < end) {

                            if ((num[start] + num[end]) == newTarget) {

                                ArrayList<Integer> temp = new ArrayList<Integer>(4);

                                temp.add(num[i]);

                                temp.add(num[j]);

                                temp.add(num[start]);

                                temp.add(num[end]);

                             

                                result.add(temp);

                                start++;

                                end--;

                                while (start < end && num[start] == num[start - 1]) start++;

                                while (start < end && num[end] == num[end + 1]) end--;

                            } else if (num[start] + num[end] < newTarget) { 

                                start++;

                            } else {

                                end--;

                            }

                        }

                    //}

                }

            //}

        }

        return result;

    }

X.Using HashMap O(N^2)
https://discuss.leetcode.com/topic/12893/on-average-o-n-2-and-worst-case-o-n-3-java-solution-by-reducing-4sum-to-2sum

Basic idea is to reduce the 4Sum problem to 2Sum one. In order to achieve that, we can use an array (size of n^2) to store the pair sums and this array will act as the array in 2Sum case (Here n is the size of the original 1D array and it turned out that we do not even need to explicitly use the n^2 sized array ). We also use a hashmap to mark if a pair sum has been visited or not (the same as in the 2Sum case). The tricky part here is that we may have multiple pairs that result in the same pair sum. So we will use a list to group these pairs together. For every pair with a particular sum, check if the pair sum that is needed to get the target has been visited. If so, further check if there is overlapping between these two pairs. If not, record the result.

Time complexity to get all the pairs is O(n^2). For each pair, if the pair sum needed to get the target has been visited, the time complexity will be O(k), where k is the maximum size of the lists holding pairs with visited pair sum. Therefore the total time complexity will be O(k*n^2). Now we need to determine the range of k. Basically the more distinct pair sums we get, the smaller k will be. If all the pair sums are different from each other, k will just be 1. However, if we have many repeated elements in the original 1D array, or in some extreme cases such as the elements form an arithmetic progression, k can be of the order of n (strictly speaking, for the repeated elements case, k can go as high as n^2, but we can get rid of many of them). On average k will be some constant between 1 and n for normal elements distribution in the original 1D array. So on average our algorithm will go in O(n^2) but with worst case of O(n^3)

public List<List<Integer>> fourSum(int[] num, int target) {
    Arrays.sort(num);
    
    Map<Integer, List<int[]>> twoSumMap = new HashMap<>(); // for holding visited pair sums. All pairs with the same pair sum are grouped together
    Set<List<Integer>> res = new HashSet<>();  // for holding the results
    
    for (int i = 0; i < num.length; i++) {
     // get rid of repeated pair sums
        if (i > 1 && num[i] == num[i - 2]) continue;
     
        for (int j = i + 1; j < num.length; j++) {
            // get rid of repeated pair sums
            if (j > i + 2 && num[j] == num[j - 2]) continue;

            // for each pair sum, check if the pair sum that is needed to get the target has been visited.             
            if (twoSumMap.containsKey(target - (num[i] + num[j]))) {   
                // if so, get all the pairs that contribute to this visited pair sum.
         List<int[]> ls = twoSumMap.get(target - (num[i] + num[j]));
          
         for (int[] pair : ls) {
             // we have two pairs: one is indicated as (pair[0], pair[1]), the other is (i, j).
             // we first need to check if they are overlapping with each other.
             int m1 = Math.min(pair[0], i);  // m1 will always be the smallest index
                    int m2 = Math.min(pair[1], j);  // m2 will be one of the middle two indices
                    int m3 = Math.max(pair[0], i);  // m3 will be one of the middle two indices
                    int m4 = Math.max(pair[1], j);  // m4 will always be the largest index
                    
                    if (m1 == m3 || m1 == m4 || m2 == m3 || m2 == m4) continue;  // two pairs are overlapping, so just ignore this case
       
       res.add(Arrays.asList(num[m1], num[Math.min(m2, m3)], num[Math.max(m2, m3)], num[m4]));  // else record the result
         }
            }
            
            // mark that we have visited current pair and add it to the corrsponding pair sum group.
            // here we've encoded the pair indices i and j into an integer array of length 2.
            twoSumMap.computeIfAbsent(num[i] + num[j], key -> new ArrayList<>()).add(new int[] {i, j});
        }
    }
    
    return new ArrayList<List<Integer>>(res);
}

http://www.lifeincode.net/programming/leetcode-two-sum-3-sum-3-sum-closest-and-4-sum-java/

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). ????

    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;

    }

http://www.sigmainfy.com/blog/4sum-problem-analysis-different-time-complexity.html
https://discuss.leetcode.com/topic/3752/my-c-solution-using-hashtable

    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        int n = num.length;
        if (n < 4)          // Contains less than four numbers
            return result;
        Arrays.sort(num);   // Sort the array in non-descending order
        // Record the sum of each pair using a map, with the sum as the key
        // and the indices of the pair as the value
        HashMap<Integer, ArrayList<Pair>> hashMap = new HashMap<Integer, ArrayList<Pair>>();
        for (int i = 0; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
                if (hashMap.containsKey(num[i]+num[j]))     // Existing sum (key)
                    hashMap.get(num[i]+num[j]).add(new Pair(i, j));
                else {              // new sum (key)
                    ArrayList<Pair> pairs = new ArrayList<Pair>();
                    pairs.add(new Pair(i, j));
                    hashMap.put(num[i]+num[j], pairs);
                }
            }
        }
        // For each unique pair (num[i],num[j]) as the first two numbers in a quadruple,
        // search the map with target-num[i]-num[j] and get the remaining two numbers without duplicates
        for (int i = 0; i < n-3; i++) {
            if (i > 0 && num[i] == num[i-1])
                // All quadruples starting with num[i] have included before
                continue;
            for (int j = i+1; j < n-2; j++) {
                if (j > i+1 && num[j] == num[j-1])
                    // All quadruples starting with (num[i],num[j]) have included before
                    continue;
                int wanted = target - num[i] - num[j];
                if (hashMap.containsKey(wanted)) {  // There is at least a pair whose sum is wanted
                    for (Pair pair : hashMap.get(wanted)) {
                        if (pair.first <= j)    // The third number has to be after the second one in the array
                            continue;
                        if (result.isEmpty() || result.get(result.size()-1).get(0) != num[i] ||
                                result.get(result.size()-1).get(1) != num[j] ||
                                result.get(result.size()-1).get(2) != num[pair.first]) {    // no duplicate
                            ArrayList<Integer> quadruple = new ArrayList<Integer>(4);
                            quadruple.add(num[i]);
                            quadruple.add(num[j]);
                            quadruple.add(num[pair.first]);
                            quadruple.add(num[pair.second]);
                            result.add(quadruple);
                        }
                    }
                }
            }
        }

        return result;
    }

http://www.lifeincode.net/programming/leetcode-two-sum-3-sum-3-sum-closest-and-4-sum-java/
3 Sum Closest

    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;

    }

http://www.cnblogs.com/tenosdoit/p/3649607.html
http://www.cnblogs.com/springfor/p/3860076.html
http://www.programcreek.com/2013/02/leetcode-4sum-java/

X. Use hashmap
http://buttercola.blogspot.com/2014/07/leetcode-4sum.html
Here I also introduced the hashMap solution, its time complexity is still O(n^3), but takes additional O(n^3) space to store the key-value pairs, which is not desirable when the storage space is constraint.

O(N^3)

4 sum跟3 sum是一样的思路，只不过需要多考虑一个加数，这样时间复杂度变为O(n3)。
使用HashSet来解决重复问题的代码如下：

 1 public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
 2     HashSet<ArrayList<Integer>> hashSet = new HashSet<ArrayList<Integer>>();
 3     ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 4     Arrays.sort(num);
 5     for (int i = 0; i <= num.length-4; i++) {
 6         for (int j = i + 1; j <= num.length-3; j++) {
 7             int low = j + 1;
 8             int high = num.length - 1;
 9  
10             while (low < high) {
11                 int sum = num[i] + num[j] + num[low] + num[high];
12  
13                 if (sum > target) {
14                     high--;
15                 } else if (sum < target) {
16                     low++;
17                 } else if (sum == target) {
18                     ArrayList<Integer> temp = new ArrayList<Integer>();
19                     temp.add(num[i]);
20                     temp.add(num[j]);
21                     temp.add(num[low]);
22                     temp.add(num[high]);
23  
24                     if (!hashSet.contains(temp)) {
25                         hashSet.add(temp);//
26                         result.add(temp);
27                     }
28  
29                     low++;
30                     high--;
31                 }
32             }
33         }
34     }
35  
36     return result;
37 }

http://lifexplorer.me/leetcode-3sum-4sum-and-k-sum/
时间复杂度O(n^2)，空间复杂度为O(n)的解法：采用分治思想，先对数组预处理，求的元素两两之和，然后采用2Sum算法思想遍历数组求的四个数字之和。

http://tech-wonderland.net/blog/summary-of-ksum-problems.html
K sum的求和问题一般是这样子描述的：给你一组N个数字(比如 vector<int> num), 然后给你一个常数(比如 int target) ，我们的goal是在这一堆数里面找到K个数字，使得这K个数字的和等于target。

方法二： 排序，这个算法可以考虑最简单的case, 2sum，这是个经典问题，方法就是先排序，然后利用头尾指针找到两个数使得他们的和等于target.

在考虑3sum, 有了2sum其实3sum就不难了，这样想：先取出一个数，那么我只要在剩下的数字里面找到两个数字使得他们的和等于(target – 那个取出的数)就可以了吧。所以3sum就退化成了2sum, 取出一个数字，这样的数字有N个，所以3sum的算法复杂度就是O(N^2 ),
那么以此类推，K-sum一步一步退化，最后也就是解决一个2sum的问题，K sum的复杂度是O(n^(K-1))

K sum的复杂度是O(n^(K-1))


Also check code at
http://tech-wonderland.net/blog/summary-of-ksum-problems.html
http://www.lifeincode.net/programming/leetcode-two-sum-3-sum-3-sum-closest-and-4-sum-java/
http://vialgorithms.blogspot.com/2013/10/2sum-3sum-4sum.html
http://blog.csdn.net/linhuanmars/article/details/24826871
Read full article from Go Tigers!: 4Sum [Leetcode]