学算法,刷力扣,加油卷,进大厂!
题目描述
力扣题目链接
给你一个由 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
涉及知识点
这是一道中等难度题目,与前面的三数之和有差不多的思路。很明显,直接for循环的暴力解法是超时的,但是对于这种我们想到的还是优化。参考三数之和的思路,我们依然可以通过使用双指针的方式来解决这道题目。
参考三数之和的解法,我们需要了解的知识点如下:
- 数组是存储在连续内存空间的相同类型数据的集合
- 数组下标都是从0开始
- 数组在内存空间的地址都是连续的
那么根据题目,我们可以提炼的关键点:
- 满足四数之和等于target
- 不重复
题目解答
Java题解一
思路分析
使用双指针法,即首先对数组排序,然后利用双指针的移动来找出满足条件的值(一共是四个指针,两个用来遍历的定指针)。具体思路如下:
- 首先排序,方便去重
- 第一个定指针 i,用来遍历(注意去重)
- 第二个定指针 j,用来遍历(注意去重)
- 开始使用双指针
- 然后是双指针的左右指针i和j,左指针i在k的后面,右指针j在数组最右边
- 在左右指针不交叉的情况下,左指针右移,右指针左移
- 满足条件加入List集合;不满足的话,移动固定指针后,重复上面步骤
代码实现如下
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
//双指针
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums); // 排序,方便去重
for(int i = 0; i < nums.length - 3; i++) { //第一个定指针
if (i > 0 && nums[i] == nums[i-1]) {
continue; // 去重
}
for (int j = i + 1; j < nums.length - 2; j++) { // 第二个定指针
if (j > i + 1 && nums[j] == nums[j-1]) {
continue; //去重
}
int left = j + 1; //左指针
int right = nums.length - 1; //右指针
while (left < right) { //满足左指针小于右指针
int sum = nums[i] + nums[j] + nums[left] + nums[right]; //sum求四数之和
if (sum == target) { //满足条件
res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
// 跳过重复
while(left < right && nums[left+1] == nums[left])
left++;
while (left < right && nums[right-1] == nums[right])
right--;
// 左指针右移
left++;
// 右指针左移
right--;
} else if (sum > target) { //如果和比目标值大,移动右指针
right--;
} else { // 如果和比目标值小,移动左指针
left++;
}
}
}
}
return res;
}
}