每天一道leetcode18- 四数之和 分类:双指针 中文链接: https://leetcode-cn.com/problems/4sum/description/ 英文链接 https://leetcode.com/problems/4sum/description/
给定一个包含 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] ]
思路
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
HashSet<List<Integer>> set = new HashSet<>();
List<List<Integer>> result = new ArrayList<>();
if(nums.length == 4)
{
if(nums[0] + nums[1] + nums[2] + nums[3] == target)
{
List<Integer> temp = new ArrayList<>();
temp.add(nums[0]);
temp.add(nums[1]);
temp.add(nums[2]);
temp.add(nums[3]);
result.add(temp);
return result;
}
return result;
}
Arrays.sort(nums);
for(int begin = 0;begin < nums.length-3;begin++)
{
for(int end = nums.length-1;end - begin > 2;end--)
{
int left = begin + 1;
int right = end - 1;
while(left < right)
{
int tempSum = nums[begin] + nums[end] + nums[left] + nums[right];
if(tempSum == target)
{
List<Integer> temp = new ArrayList<>();
temp.add(nums[begin]);
temp.add(nums[left]);
temp.add(nums[right]);
temp.add(nums[end]);
set.add(temp);
left++;
}else if(tempSum < target)
left++;
else
right--;
}
}
}
for(List<Integer> t: set)
result.add(t);
return result;
}
}
代码讲解