四数之和
题目描述
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
思路
首先判断两种特殊情况，1：数组长度小于4，2：最小四个数只和大于target
这题用枚举+贪心，枚举出前两个数的所有情况，其中如果遇到重复的数要跳过，在跳过时要注意i>0而j>i+1
将前两个数枚举之后，后两个数用贪心，左右指针分别指向第一个与最后一个
如果四数和等于target，则存储
大于target，则右指针左移，跳过重复情况，说明最后一个数太大要减小
小于target，则左指针右移，跳过重复情况
Java实现
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if(nums.length<=3){
return ans;
}
Arrays.sort(nums);
int minn = nums[0]+nums[1]+nums[2]+nums[3];
if(minn>target){
return ans;
}
for(int i=0;i<=nums.length-4;i++){
if(i>0&&nums[i]==nums[i-1]) continue;
for(int j=i+1;j<=nums.length-3;j++){
if(j>i+1&&nums[j]==nums[j-1]) continue;
int left=j+1,right=nums.length-1;
while(left<right){
if(nums[i]+nums[j]+nums[left]+nums[right]==target){
ans.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
left++;
right--;
while(left<nums.length&&nums[left]==nums[left-1]) left++;
while(right>j&&nums[right]==nums[right+1]) right--;
} else if(nums[i]+nums[j]+nums[left]+nums[right]<target){
left++;
} else {
right--;
}
}
}
}
return ans;
}
执行用时 :52 ms, 在所有 Java 提交中击败了76.29%的用户
内存消耗 :38.5 MB, 在所有 Java 提交中击败了89.43%的用户
