LeetCode 18 - 4Sum

nSum

作者 QIFAN 日期 2017-01-13
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++;
}
}
}