leetcode: 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)

原问题链接：https://leetcode.com/problems/4sum/

 

问题分析

    这个问题的解决方法有好几种，一种是基于前面3sum的办法再加一个循环来解决。还有一种是基于前面一篇文章讨论过的方法。

     虽然前面讨论的很多方法在理论上比较好，在实际问题结合具体的情况时还有更多可以优化改进的地方。像前面提到的3Sum等问题，我们都是针对数组排序，然后在一定的范围内循环取值来规避一些重复的情况。因为题意的要求需要去除重复的项，这也是这个问题里可以优化的地方。我们先不按照前面的3Sum办法套循环，而是根据这个问题的情况来具体分析一下。

 

方法一

    对于4Sum来说，它需要有4个元素a + b + c + d = target。所以我们这里相当于找到两个数的和，然后再找是否有另外两个不同的数字它们的和和前面这两个加起来等于target。而要求得所有数字的和的组合，我们无非就是用一个两重的循环就可以得出来。在这里我们可以借鉴一下2Sum的解决办法。

    我们可以用一个map来保存两个元素的和。其中map的key是两个数的和，value则保存这两个数在数组里的索引。因为要保存两个数字的结构，这里可以用现成的AbstractMap.SimpleEntry。也可以自己定义一个Pair的类型。由于存在有不同的两个数的和是同一个值的情况，所以我们要用一个List来保存所有的这些数字对。这样我们每次取得一个数字组合的时候就去map里查找是否存在有target - nums[i] - nums[j]的元素。如果有的话，则说明找到了符合条件的元素。

    这样的话，我们就需要把map里这个元素对应的list元素都拿出来，和i, j 组成一个数组。这里还有一个需要判断过滤的地方。就是要防止list里面元素对和i, j有相同的。因为可能有元素索引1, 2它的和正好和索引1, 3它们的和构成target，但是这是不符合条件的。在构成这个数组后我们还需要在最终的结果里判断去除重复的数组。这样才得到最终的结果。

    按照这个思路，我们可以得到如下的代码：

 

import static java.util.AbstractMap.SimpleEntry;

public class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        if(num.length < 4) return new ArrayList();
        Map<Integer, List<SimpleEntry<Integer, Integer>>> map = new HashMap<Integer, List<SimpleEntry<Integer, Integer>>>();
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Arrays.sort(num);
        for(int i = 0; i < num.length; i++) {
            for(int j = i + 1; j < num.length; j++) {
                if(map.containsKey(target - num[i] - num[j])) {
                    for(SimpleEntry<Integer, Integer> entry : map.get(target - num[i] - num[j])) {
                        if(entry.getKey() != i && entry.getKey() != j && entry.getValue() != i && entry.getValue() != j) {
                            List<Integer> list = new ArrayList<Integer>();
                            list.add(num[entry.getKey()]);
                            list.add(num[entry.getValue()]);
                            list.add(num[i]);
                            list.add(num[j]);
                            Collections.sort(list);
                            if(!result.contains(list)) result.add(list);
                        }
                    }
                }
                if(map.containsKey(num[i] + num[j])) {
                    map.get(num[i] + num[j]).add(new SimpleEntry(i, j));
                } else {
                    List<SimpleEntry<Integer, Integer>> item = new ArrayList<SimpleEntry<Integer, Integer>>();
                    item.add(new SimpleEntry(i, j));
                    map.put(num[i] + num[j], item);
                }
            }
        }
        return result;
    }
}

    上述代码的逻辑还是比较简单的。它的时间复杂度为O(N^3)。

 

方法二

    和上述方法的思路不同，我们这里如果换一种思路，稍微借鉴了一部分3Sum的办法。我们可以这么来想。既然我们是要找4个不同的元素，而且希望最终的结果是从小到大的方式来排列。如果事先将数组排序之后。我们要求的这4个元素必然会构成一个从小到大的顺序。我们不需要关注哪个在前面哪个在后面。那么我们可以考虑一种取两头，然后往中间凑的方式。

    这就好比是首先我们取数组的两头的两个元素，假设它们是我们找到的两个元素nums[i]   , nums[j] (i < j)。如果真的有构成4个元素的和等于target的话，必然有两个元素在i, j之间。这个时候我们就只需要从i + 1到j - 1的范围内去排查就可以了。这个排查的过程就和3sum里的思路差不多。考虑到从i, j两头凑的方法最终要满足有4个元素，所以必然要有j > i + 2。我们要针对所有可能的i, j范围去遍历，i的取值范围是0到nums.length - 4。而j则取i + 3到 nums.length - 1。

     在实际的实现代码里，我们还有一些可以优化的地方，比如当nums[i] * 4 > target的时候，我们可以直接退出。因为这里i就是最小的元素，它的4倍已经大于target了那么就没有查找的必要了。同样，如果nums[j] * 4 < target 也可以退出当前循环。另外还有一些小的优化手段，像3Sum里的那样，当找到两个元素的和等于目标值了。针对这两个元素它和它后面的值作比较，跳过一些相同的值。

    按照这个思路，可以得到如下的代码：

 

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0, len = nums.length; i < len - 3; i++) {
            if(nums[i]<<2 > target) return list; // return immediately
            for(int j = len - 1; j > i + 2; j--) {
                if(nums[j]<<2 < target) break; // break immediately
                int rem = target - nums[i] - nums[j];
                int l = i + 1, r = j - 1;
                while(l < r) {
                    int sum = nums[l] + nums[r];
                    if(sum > rem) --r;
                    else if(sum < rem) ++l;
                    else {
                        list.add(Arrays.asList(nums[i], nums[l], nums[r], nums[j]));
                        while(++l <= r && nums[l - 1] == nums[l]); // avoid duplicate results
                        while(--r >= l && nums[r] == nums[r + 1]); // avoid duplicate results
                    }
                }
                while(j >= 1 && nums[j] == nums[j - 1]) --j; // skip inner loop
            }
            while(i < len - 1 && nums[i] == nums[i + 1]) ++i; // skip outer loop
        }
        return list;
    }
}

     虽然从时间复杂度来说，这种思路也是理论上达到O(N^3)的结果。但是由于这里省略了要对结果的排序和去除重复。所以执行的效率大大提高。

 

自己的最初实现

     一般来说，到这里就应该结束了。不过觉得在这里将自己最初的一个实现效率比较低的方法列出来作为比较发现一些原有实现上效率低下的地方也是很好的。

    原有的方法和前面文章里讨论4Sum的思路比较一致，首先根据所有元素的和的情况去得到一个n * (n - 1) / 2的数组。这个数组里保存的是原nums数组所有元素任意两个值的和的所有情况。然后我们再对这个数组排序。然后再按照3Sum里的思路去查找合适的对，再去除重复的索引以及数组。

    这种实现的代码如下：

 

import static java.util.AbstractMap.SimpleEntry;

public class Solution {
    private Map<Integer, List<SimpleEntry<Integer, Integer>>> map = new HashMap<>();
    private int[] medium;
    private List<List<Integer>> result = new ArrayList<>();
    
    public List<List<Integer>> fourSum(int[] nums, int target) {
        makeMap(nums);
        Arrays.sort(medium);
        int l = 0, r = medium.length - 1;
        while(l < r) {
            if(medium[l] + medium[r] == target) {
                mergeList(medium[l], medium[r], nums);
                l++;
                r--;
            } else if(medium[l] + medium[r] < target) {
              l++;
              while(l < r && medium[l] == medium[l - 1]) l++;
            } else {
                r--;
                while(l < r && medium[r] == medium[r + 1]) r--;
            }
        }
        return result;
    }

    public void makeMap(int[] nums) {
        int n = nums.length, k = 0;
        int size = n * (n - 1) / 2;
        medium = new int[size];
        for(int i = 0; i < nums.length - 1; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                int key = nums[i] + nums[j];
                SimpleEntry<Integer, Integer> entry = new SimpleEntry<>(i, j);
                if(map.containsKey(key)) {
                    map.get(key).add(entry);
                } else {
                    List<SimpleEntry<Integer, Integer>> list = new ArrayList<>();
                    list.add(entry);
                    map.put(key, list);
                }
                medium[k++] = key;
            }
        }
    }

    
    public void mergeList(int l, int r, int[] nums) {
        for(SimpleEntry<Integer, Integer> entry : map.get(l)) {
            for(SimpleEntry<Integer, Integer> e : map.get(r)) {
                List<Integer> list = new ArrayList<>();
                if(entry.getKey() == e.getKey() || entry.getKey() == e.getValue() ||
                    entry.getValue() == e.getKey() || entry.getValue() == e.getValue()) continue;
                list.add(nums[entry.getKey()]);
                list.add(nums[entry.getValue()]);
                list.add(nums[e.getKey()]);
                list.add(nums[e.getValue()]);
                Collections.sort(list);
                if(!result.contains(list)) result.add(list);
            }
        }
    }
}

     很显然，这种方法的思路是好的。希望将所有和的情况都记录下来分析。而这里导致效率低下的地方在于一方面要保存一个map，里面有所有和以及元素对列表。同时还要建立一个长的和值数组，并对这个n * n级别的数组排序。而这里很多情况在上述的实现里是可以很好避免的。

 

总结

    仅仅知道一些问题的思路还是远远不够的，结合具体问题的分析和实现往往能发现一些更加高效的实现。