四数之和
# 📃 题目描述
题目链接:18. 四数之和 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] :
- 0 <= a, b, c, d < n
- a、b、c 和 d 互不相同
- nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2:
输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]
# 🔔 解题思路
# 哈希表
仿照上面 15. 三数之和 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 的题解,对于这题我们通过三层 for 循环固定三个元素,然后在哈希表中找第三个元素:
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
// 存储四元组
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 4) {
return res;
}
// 对数组进行排序
Arrays.sort(nums);
// key: 数组元素, value: 该元素对应的下标
Map<Integer, Integer> map = new HashMap<>();
// 将数组存入 map, 相等的值只会放进去一个,
for (int i = 0; i< nums.length; i ++) {
map.put(nums[i], i);
}
// 三层循环决定 a b c
// 遍历获得 a
for (int i = 0; i < nums.length; i ++) {
// 对 a 进行去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 遍历获得 b
for (int j = i + 1; j < nums.length; j ++) {
// 对 b 进行去重
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// 遍历获得 c
for (int k = j + 1; k < nums.length; k ++) {
// 对 c 进行去重
if (k > j + 1 && nums[k] == nums[k - 1]) {
continue;
}
// map 中查找最后一个数 d
int temp = target - nums[i] - nums[j] - nums[k];
if (map.containsKey(temp) && map.get(temp) > k) {
res.add(Arrays.asList(nums[i], nums[j], nums[k], temp));
}
}
}
}
return res;
}
}
需要注意的是,在三数之和那道题目中,我们做了一个剪枝操作,即排序之后如果第一个元素已经大于零,那么不可能凑成三元组,直接 break 即可。但是这道题目的 target 不是 0,且有可能是负数,所以这个剪枝操作不能再用了。
举个例子,[1,-2,-5,-4,-3,3,3,5],排序后,[-5,-4,-3,-2, 1, 3, 3, 3, 5],target = -11,虽然第一个数 -5 就已经大于 -11 了,但是负数相加会越来越小,所以这里不能直接返回!
- 空间复杂度:空间复杂度为 O(N^2)(如果我们忽略掉用于存储答案的空间,那么该算法的空间复杂度主要来自于排序,额外的排序的空间复杂度为 O(logN))
- 时间复杂度:排序时间复杂度为 O(NLogN),三层循环的时间复杂度为 O(N^3),所以总的时间复杂度是 O(N^3)
# 双指针
双指针法做这道题目会更简单。思路如下:
1)对数组进行排序
2)两层循环遍历排序后的数组,确定前两个元素 nums[i] 和 nums[j]
若 nums[i] > target,由于数组已经有序,所以它后面的一定也 > target,直接返回(这题不能直接返回哦,因为 target 不是 0!上面已经举过例子了)- 对于重复元素,跳过
- 两个指针,左指针 left 指向 j + 1,另一个右指针 right 指向数组的最后一个元素:
- 若 nums[i] + nums[j] + nums[left] + nums[right] = target,说明这四个就是符合要求的元组。然后 left ++,right -- 寻找新的解(需要注意的是,在移动的过程中,记得进行去重,跳过重复元素)
- 若 nums[i] + nums[j] + nums[left] + nums[right] < target,left ++
- 若 nums[i] + nums[j] + nums[left] + nums[right] > target,right --
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
// 存储四元组
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 4) {
return res;
}
// 对数组进行排序
Arrays.sort(nums);
// 两层循环遍历排序后的数组,确定前两个元素 nums[i] 和 nums[j]
for (int i = 0; i < nums.length; i ++) {
// 跳过重复元素
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length; j ++) {
// 跳过重复元素
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// 找到剩下的两个元素
int left = j + 1;
int right = nums.length - 1;
while (left < right) {
long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
// 跳过重复元素
while (left < right && nums[left] == nums[left + 1]) {
left ++;
}
while (left < right && nums[right] == nums[right - 1]) {
right --;
}
// 开始寻找新的解
left ++;
right --;
} else if (sum < target) {
left ++;
} else {
right --;
}
}
}
}
return res;
}
}
# 💥 复杂度分析
- 空间复杂度:O(N^2)(如果我们忽略掉用于存储答案的空间,那么该算法的空间复杂度主要来自于排序,额外的排序的空间复杂度为 O(logN))
- 时间复杂度:O(N^3)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10