LeetCode 0018 - 4Sum
# Hints
- 思维 + 暴力枚举 + 双指针扫描
# 前置题目
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given an array of integers and an integer , are there elements in such that ? Find all unique quadruplets in the array which gives the sum of .
Note:
The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [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]
]
# 题意
给定一个长为 的数组,给定一个整数 ,求出所有的四元组 ,满足 。要求返回的结果中没有重复的四元组,且每个四元组内部都是有序的。
# 题解
本题类似于Leetcode 0015,仍可用类似的方法解决,只是细节上有所差别。
在3-sum问题中,我们首先枚举 ,然后在后半部分求取合法的二元组 。现在我们只需枚举 和 ,然后在后半部分求取合法的二元组 即可,总的时间复杂度为 。至于去重和求解2-sum问题的方法,和3-sum问题的求解都是一样的。
为提高效率还可加入一些剪枝操作,主要是利用了 的有序,但这些并不会改变最坏时间复杂度:
在枚举 时,如果 ,则此后的任意一个四元组之和都将大于 ,可立即终止求解。
在枚举 时,如果 ,说明 的值太小,可直接跳过当次循环。
在枚举 时可使用类似的两种剪枝,原理相同,因而不予赘述。
# AC代码
class Solution {
public:
vector<vector<int>> fourSum(vector<int> & nums, int target) {
// 特判
if (nums.size() < 4) {
return vector<vector<int>>();
}
// 排序
sort(nums.begin(), nums.end());
// 暴力枚举
vector<vector<int>> res;
int n = nums.size();
for (int i = 0; i < n - 3; i ++) {
// 去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 剪枝
if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
continue;
}
// 暴力枚举
for (int j = i + 1; j < n - 2; j ++) {
// 去重
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// 剪枝
if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
if (nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
continue;
}
// 求解
vector<vector<int>> vec = twoSum(nums, i, j, target - nums[i] - nums[j]);
// 更新答案
res.insert(res.end(), vec.begin(), vec.end());
}
}
// 返回
return res;
}
// 求解2-sum问题(有序)
vector<vector<int>> twoSum(vector<int> & nums, int index1, int index2, int target) {
// 主循环
vector<vector<int>> res;
int left = index2 + 1, right = (int)nums.size() - 1;
while (left < right) {
// 求和
int sum = nums[left] + nums[right];
// 相等的情况
if (sum == target) {
// 更新答案
res.push_back(vector<int>({nums[index1], nums[index2], nums[left], nums[right]}));
// 递进
left ++;
right --;
// 去重
while (left < right && nums[left] == nums[left - 1]) { // && left > 0
left ++;
}
while (left < right && nums[right] == nums[right + 1]) { // && right < (int)nums.size() - 1
right --;
}
} else {
// 递进
if (sum < target) left ++;
if (sum > target) right --;
}
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01