题目描述
给你一个由 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]]
提示：
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
题目评估
官方难度：中等
知识点：数组、双指针、排序
分析
四数之和加起来等于指定值，暴力需要四重循环时间肯定不够，那可以排序后让最里层两层循环双指针遍历，最外两层依然暴力遍历，并且因为是排序后的数组，在每层循环中可以跳过和上次重复的数字。
Java代码题解
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new LinkedList<>();
int len = nums.length;
if (len < 4) {
return res;
}
Arrays.sort(nums);
// 如果最小的四个数加起来都大于目标值就没有答案
if ((long)nums[0] + nums[1] + nums[2] + nums[3] > target) {
return res;
}
// 如果最大的四个数加起来仍小于目标值也没有正确答案
if ((long)nums[len - 1] + nums[len - 2] + nums[len - 3] + nums[len - 4] < target) {
return res;
}
// 从后向前遍历
for (int i = len - 1; i >= 3; i--) {
if (i != len - 1 && nums[i] == nums[i + 1]) {
continue;
}
for (int j = i - 1; j >= 2; j--) {
// 去重
if (j != i - 1 && nums[j] == nums[j + 1]) {
continue;
}
// 当最外两层却确定时，与剩余两个最小的值加起来都大于目标值，说明最外两层的数字太大了，直接continue第二层
if ((long)nums[i] + nums[j] + nums[0] + nums[1] > target) {
continue;
}
// 当最外两层却确定时，与剩余两个最大的值加起来都小于目标值，说明以后再也没有能加起来等于目标值的了，直接结束
if ((long)nums[i] + nums[j] + nums[j - 1] + nums[j - 2] < target) {
break;
}
// 定义双指针
int x = 0;
int y = j - 1;
while (x < y) {
// 求和
int sum = nums[i] + nums[j] + nums[x] + nums[y];
if (sum == target) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[x]);
list.add(nums[y]);
res.add(list);
}
// 滑动指针
if (sum > target) {
y--;
while (x < y && nums[y] == nums[y + 1]) {
y--;
}
} else {
x++;
while (x < y && nums[x] == nums[x - 1]) {
x++;
}
}
}
}
}
return res;
}
}
复杂度分析
时间复杂度：O(n^3)，其中 n 是数组的长度。排序的时间复杂度是 O(nlogn)，枚举四元组的时间复杂度是 O(n^3)，因此总时间复杂度为 O(n^3 + nlogn) = O(n^3)。
空间复杂度：O(logn)，其中 n 是数组的长度。空间复杂度主要取决于排序额外使用的空间。此外排序修改了输入数组 nums，实际情况中不一定允许，因此也可以看成使用了一个额外的数组存储了数组 nums 的副本并排序，空间复杂度为O(n)。