本文主要是介绍Leetcode18 四数之和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
给定一个包含 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
输出:[]
思路分析:
四数之和相比于三数之和,同样还是采用双指针的做法,仅是多了层循环,多加两个定位前两个数的条件而已
- 判断数组长度是否大于四
- 为了方便采用双指针方法去判断四数之和与target的关系,需要去排序。
- 因为是四数,所以第一个元素位置要小于nums.length-3,第二个要小于nums.length-2。
- 在三数之和的基础上加层循环,依旧需要考虑去重问题,过滤掉无用信息
例如:
//当最小的四个数大于最大值时就没必要继续,跳出循环if((nums[i]+nums[i+1]+nums[i+2]+nums[i+3])>target){break;}//当最小的值和三个最大值之和小于target时,变化最小的,继续进行比较即可//定位第二个位置的数的与定位第一个数的位置相同,其它步骤就是三数之和操作。 if((nums[i]+nums[len-1]+nums[len-2]+nums[len-3])<target){continue;}
public List<List<Integer>> fourSum(int[] nums, int target) {List<Integer> list =null;List<List<Integer>> lList=new ArrayList<>();int len=nums.length;if(len<4){return lList;//数组长度小于4不符合要求}Arrays.sort(nums);for(int i=0;i<len-3;i++){//通过移动第一个元素去控制后三个元素的移动if(i>0&&nums[i]==nums[i-1]){continue;} if((nums[i]+nums[i+1]+nums[i+2]+nums[i+3])>target){//四个最小的大于target,结束break;}if((nums[i]+nums[len-1]+nums[len-2]+nums[len-3])<target){//最小的加三个最大的小于target,只能调整icontinue;}for(int j=i+1;j<len-2;j++) {//-4,-1,-1,0,1,2if(j>i+1&&nums[j]==nums[j-1]){continue;}if((nums[i]+nums[j]+nums[j+1]+nums[j+2])>target){//四个最小的大于target,结束break;}if((nums[i]+nums[j]+nums[len-1]+nums[len-2])<target){//最小的加三个最大的小于target,只能调整jcontinue;}int left=j+1;//-4,-1,-1,0,1,2int right=len-1;while(left<right){if(nums[i]+nums[j]+nums[left]+nums[right]>target){right--;}else if(nums[i]+nums[j]+nums[left]+nums[right]<target){left++;}else{list=new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[left]);list.add(nums[right]);lList.add(list);//以下两个while循环是去重操作while(left<right&&nums[right]==nums[right-1]){right--;}while(left<right&&nums[left]==nums[left+1]){left++;}left++;right--;}}} }return lList; }
这篇关于Leetcode18 四数之和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!