LeetCode 18 - 4Sum

nSum

作者 QIFAN 日期 2017-01-13
LeetCode Array
LeetCode 18 - 4Sum

原题链接：18. 4Sum

啊哈哈哈十分开心攻克了这道题！

题干

给定一个数组 S ，其中是否有四个数 a ， b ， c ， d 满足 a + b + c + d = 0 ？ 返回所有不重复的组合。

思路

思路就是在 3Sum 外面再多套一层。顺便受 7ms java code win over 100% 启发，改进了一下之前的 3Sum ，把时间复杂度变成了 $O(N^2)$ ，所以最后 4Sum 的时间复杂度就是 $O(N^3)$ 。

本题的要细心的地方在于怎么去避免重复结果的产生。另外在一些临界点作出判断避免无效的计算。

代码：

public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> res = new ArrayList<>();
    if (nums.length < 4) {
        return res;
    }
    Arrays.sort(nums);
    if (4 * nums[nums.length - 1] < target) {
        return res;
    }
    int max3Sum = 3 * nums[nums.length - 1];
    int lastsize = res.size();
    for (int i = 0; i < nums.length - 3; i++) {
        // 先初步判断排除一些情况：
        // 1. 上一个数与这次的数一样
        if (i > 0 && nums[i - 1] == nums[i]) {
            continue;
        }
        // 2. 数太大
        if (nums[i] * 4 > target) {
            break;
        }
        // 3. 数太小
        if (nums[i] + max3Sum < target) {
            continue;
        }
        //System.out.println("3sum for " + (target - nums[i]));
        
        threeSum(res, nums, target - nums[i], i + 1);
        // 在 threeSum 后新加的集合里添加 nums[i]
        while (lastsize < res.size()) {
            res.get(lastsize).add(nums[i]);
            lastsize++;
        }
    }
    return res;
}
private void threeSum(List<List<Integer>> res, int[] nums, int target, int lo) {
    int max2Sum = 2 * nums[nums.length - 1];
    int lastsize = res.size();
    for (int i = lo; i < nums.length - 2; i++) {
        // 先初步判断排除一些情况：
        // 1. 上一个数与这次的数一样 
        if (i > lo && nums[i] == nums[i - 1]) {
            continue;
        }
        // 2. 数太大
        if (nums[i] * 3 > target) {
            break;
        }
        // 3. 数太小
        if (nums[i] + max2Sum < target) {
            continue;
        }
        //System.out.println("2sum for " + (target - nums[i]));
        twoSum(res, nums, target - nums[i], i + 1);
        // 在 twoSum 后新加的集合里添加 nums[i]
        while (lastsize < res.size()) {
            res.get(lastsize).add(nums[i]);
            lastsize++;
        }
        
    }
}
private void twoSum(List<List<Integer>> res, int[] nums, int target, int lo) {
    int hi = nums.length - 1;
    while (lo < hi) {
        if (2 * nums[lo] > target || 2 * nums[hi] < target) {
            break;
        }
        int sum = nums[lo] + nums[hi];
        //System.out.println("sum is " + sum);
        
        // 找到
        if (sum == target) {
            List<Integer> tuple = new ArrayList<>();
            tuple.add(nums[lo]);
            tuple.add(nums[hi]);
            res.add(tuple);
            lo++;
            hi--;
            // 排除重复
            while (lo < hi && nums[lo - 1] == nums[lo]) {
                lo++;
            }
            while (lo < hi && nums[hi + 1] == nums[hi]) {
                hi--;
            }
        } else if (sum > target) {
            hi--;
        } else {
            lo++;
        }
    }
}

nSum

写完之后注意到 threeSum 与 fourSum 代码极度相似，于是重构了一下，通过递归可以计算 nSum 。时间复杂度为 $O(N^n)$ 。

public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> res = new ArrayList<>();
    if (nums.length < 4) {
        return res;
    }
    Arrays.sort(nums);
    if (4 * nums[nums.length - 1] < target) {
        return res;
    }
    nSum(4, res, nums, target, 0);
    return res;
}
private void nSum(int n, List<List<Integer>> res, int[] nums, int target, int lo) {
    // base case
    if (n == 2) {
        twoSum(res, nums, target, lo);
        return;
    }
    int maxSum = (n - 1) * nums[nums.length - 1];
    int lastsize = res.size();
    for (int i = lo; i <= nums.length - n; i++) {
        // 先初步判断排除一些情况：
        // 1. 上一个数与这次的数一样 
        if (i > lo && nums[i] == nums[i - 1]) {
            continue;
        }
        // 2. 数太大
        if (nums[i] * n > target) {
            break;
        }
        // 3. 数太小
        if (nums[i] + maxSum < target) {
            continue;
        }
        nSum(n - 1, res, nums, target - nums[i], i + 1);
        // 在 nSum 后新加的集合里添加 nums[i]
        while (lastsize < res.size()) {
            res.get(lastsize).add(nums[i]);
            lastsize++;
        }       
    }
}
private void twoSum(List<List<Integer>> res, int[] nums, int target, int lo) {
    int hi = nums.length - 1;
    while (lo < hi) {
        if (2 * nums[lo] > target || 2 * nums[hi] < target) {
            break;
        }
        int sum = nums[lo] + nums[hi];
        
        // 找到
        if (sum == target) {
            List<Integer> tuple = new ArrayList<>();
            tuple.add(nums[lo]);
            tuple.add(nums[hi]);
            res.add(tuple);
            lo++;
            hi--;
            // 排除重复
            while (lo < hi && nums[lo - 1] == nums[lo]) {
                lo++;
            }
            while (lo < hi && nums[hi + 1] == nums[hi]) {
                hi--;
            }
        } else if (sum > target) {
            hi--;
        } else {
            lo++;
        }
    }
}
FEATURED TAGS
LeetCode Array
FRIENDS