潜江seo,大连seo外包,延安市建设厅网站,wordpress文档阅读器题目描述
给定一个包含 n 个整数的数组 nums 和一个目标值 target#xff0c;判断 nums 中是否存在四个元素 a#xff0c;b#xff0c;c 和 d #xff0c;使得 a b c d 的值与 target 相等#xff1f;找出所有满足条件且不重复的四元组。 注意#xff1a;答案中不可以…题目描述
给定一个包含 n 个整数的数组 nums 和一个目标值 target判断 nums 中是否存在四个元素 abc 和 d 使得 a b c d 的值与 target 相等找出所有满足条件且不重复的四元组。 注意答案中不可以包含重复的四元组。 题意 这道题是求四个数的和相加等于目标值然后要把重复的值去掉。 这个题的思路和力扣15-三数之和的思路类似三数之和是固定一个数其余进行双指针。四数之和是固定两个数其余进行双指针。
解题思路
参考官方题解
排序双指针先给数组nums进行升序排序两个for循环确定前两个数然后使用双指针确定后两个数需要考虑以下几种情况进行剪枝
在确定第一个数之后如果nums[i] nums[i1] nums[i2] nums[i3] target 代表第一个数与之邻进的三个最小数之和都大于目标值了则说明后面剩下的三个数无论取什么值四数之和一定大于target则需要退出第一轮循环 在确定第一个数之后如果nums[i] nums[n-3] nums[n-2] nums[n-1] target 代表第一个数与数组中的三个最大数之和都小于目标值了则说明后面剩下的三个数无论取什么值四数之和一定小于target则需要进入下一轮循环枚举nums[i1] 在确定前两个数之后如果nums[i] nums[j] nums[j1] nums[j2] target 说明剩下的两个数无论取什么值四个数之和一定会大于taret因此退出第二层循环 在确定前两个数之后如果nums[i] nums[j] nums[n-2] nums[n-1] target 说明剩下的两个数无论取什么值四个数之和一定会小于taret因此进入下一轮枚举nums[j1] 使用双指针左右指针分别指向下标 j1和下标 n-1。每次计算四个数的和sum并进行如下操作
如果和 sum target则将枚举到的四个数加到答案中然后将左指针右移直到遇到不同的数将右指针左移直到遇到不同的数
如果和sum target则将左指针右移一位
如果和sum target则将右指针左移一位。
public ListListInteger fourSum(int[] nums, int target) {ListListInteger res new ArrayListListInteger();int n nums.length;//如果数组的长度小于4if(n 4) return res;//对数组进行排序Arrays.sort(nums);//第一个数只能遍历到倒数第4位for(int i 0; i n-3; i){//先去掉重复值if(i 0 nums[i] nums[i-1]) continue;//如果邻近的四个数大于target,则退出if((long)nums[i] nums[i1] nums[i2] nums[i3] target) break;//如果与最大的三个数相加小于target,则说明nums[i]小了需要进入新一轮循环if((long)nums[i] nums[n-3] nums[n-2] nums[n-1] target) continue;//确定第二个数for(int j i1; j n-2; j){
//去重if(j i 1 nums[j] nums[j - 1]) continue;if((long)nums[i] nums[j] nums[j1] nums[j2] target) break;if((long)nums[i] nums[j] nums[n-2] nums[n-1] target) continue;//确定了两个数之后后两个数使用双指针int L j 1;int R n - 1;while(L R){int sum nums[i] nums[j] nums[L] nums[R];if(sum target){res.add(Arrays.asList(nums[i], nums[j], nums[L], nums[R]));//跳过重复数while(L R nums[L] nums[L 1]) L;while(L R nums[R] nums[R - 1]) R--;L;R--;}else if(sum target){L;}else{R--;}}}}return res;}
