题目
四数之和
https://leetcode-cn.com/problems/4sum/
公众号 《java编程手记》记录JAVA学习日常，分享学习路上点点滴滴，从入门到放弃，欢迎关注
描述
难度：中等
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + 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 = [], target = 0
输出：[]
提示：
0 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
Solution
双指针解法
解题思路
题目条件
跟昨天写的三数之和差不多，唯一不同的点在于，这题求得是四数之和，趁热打铁，还是按照之前的三数之和的思路
暴力解法我就不讲了，直接多重FOR循环遍历求值即可，找到小于当前最小值的就替换，这个方案在三数之和就超时了，四数就不用想了
还是使用之前双指针的方式
- 我们先将
nums进行从小到大的排序，对排序后的数组循环遍历， - 不同的是，
四数比之前的三数多了一数，这多的一数我们通过再增加一层FOR循环来实现即可 - 使用
I和J分别表示第一层和第二层循环 - 使用双指针分别指向当前
nums[j]的右侧和nums数组的最右侧 - 计算
nums[i] + nums[i] + nums[left] +nums[right]的值-
nums[i] + nums[i] + nums[left] +nums[right]> target，当前总值大于target值 ，在上一步已经进行了由小到大的排序，则需要Right的指针左移` -
nums[i] + nums[i] + nums[left] +nums[right] - target = 0- 记录到最终结果中
- 判断下一个
Left OR Right是否相等，相等则跳过，去重，防止重复
-
nums[i] + nums[i] + nums[left] +nums[right]，当总值小于target值，则需要Left的指针右移
-
- 当
Left == RIght时，遍历终止，进入下一个i的遍历查找
image-20210424103626024
CODE
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
//最终结果
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
int len = nums.length;
//第一层i
for(int i=0; i < len-3 ; i++){
//第一层如果重叠的话直接跳过，i>0,防止第一次遍历就跳过了,同时使用i-1，防止数组越界，比如[1,1,2,3,4]，第二个1就会被跳过
if(i>0&&nums[i]==nums[i-1]) continue;
//第二层j
for(int j=i+1;j<len-2;j++){
//第二层如果重叠的话直接跳过，这里需要判断j>i+1,防止第一次遍历就跳过了，j-1防止数组越界，[1,2,2,3,4]，第二个2就会被跳过
if(j>i+1&&nums[j]==nums[j-1]) continue;
//左指针
int left = j+1;
//右指针
int right = len-1;
//左指针<右指针
while(left < right){
//总值大于target，右指针左移
if(nums[i]+nums[left]+nums[right]+nums[j]>target){
right--;
//总值小于target，左指针右移
}else if(nums[i]+nums[left]+nums[right]+nums[j]<target){
left++;
}else{
//相等则添加到结果中
list.add(Arrays.asList(nums[i],nums[left],nums[right],nums[j]));
//重复的left值，直接left右移
while(left < right&&nums[left]==nums[left+1]){
left++;
}
//重复的right值，直接right左移1
while(left < right&&nums[right]==nums[right-1]){
right--;
}
right--;
left++;
}
}
}
}
return list;
}
}
复杂度
- 时间复杂度：
O(N^3)
结果
-
执行用时：
24ms, 在所有Java提交中击败了25.09%的用户内存消耗：
38.8MB, 在所有Java提交中击败了59.82%的用户
LeetCode名句
如果暴力不是证明自己有多蠢，那将毫无意义
