题目
给定一个包含 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
解法
思路: 这道题和《每日算法-三数之和》的思路差不多,只是需要先固定住两个元素,再双指针的方式查找另外两个元素。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
if(nums == null || nums.length == 0){
return result;
}
// 排序
Arrays.sort(nums);
for(int i = 0 ; i < nums.length - 3 ; i++){
// 排除重复元素
if(i != 0 && nums[i] == nums[i-1]){
continue;
}
int newTarget = target - nums[i];
for(int j = i + 1 ; j < nums.length - 2 ; j++){
// 排除重复元素
if(j > i + 1 && nums[j] == nums[j-1]){
continue;
}
int newTarget2 = newTarget - nums[j];
int left = j + 1 , right = nums.length - 1;
while(left < right){
if(nums[left] + nums[right] == newTarget2){
result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
left++;
right--;
// 排除重复元素
while(left < right && nums[left] == nums[left-1]) left++;
while(left < right && nums[right] == nums[right+1]) right--;
} else if (nums[left] + nums[right] < newTarget2){
left++;
} else {
right--;
}
}
}
}
return result;
}
}
本站文章版权归原作者及原出处所有 。内容为作者个人观点, 并不代表本站赞同其观点和对其真实性负责,本站只提供参考并不构成任何投资及应用建议。本站是一个个人学习交流的平台,网站上部分文章为转载,并不用于任何商业目的,我们已经尽可能的对作者和来源进行了通告,但是能力有限或疏忽,造成漏登,请及时联系我们,我们将根据著作权人的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。