新网网站建设资料,营销网络是什么,如何查看网站推广做的好,个人作品集网站模板一、做题链接#xff1a;18. 四数之和 - 力扣#xff08;LeetCode#xff09;
二、题目分析
1.做这一道题之前本博主建议先看上一篇《三数之和》 2.题目分析 给你一个由 n 个整数组成的数组 nums #xff0c;和一个目标值 target 。请你找出并返回满足下述全部条件且不重…一、做题链接18. 四数之和 - 力扣LeetCode
二、题目分析
1.做这一道题之前本博主建议先看上一篇《三数之和》 2.题目分析 给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复 0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[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 [2,2,2,2,2], target 8
输出[[2,2,2,2]] 由题可知做这个题要主要面临的困难是去重和漏选去重主要利用的是排序set等漏选就枚举
示例解析[1,0,-1,0,-2,2]-排序后[-2,-1,0,0,1,2] 以此类推得出最终答案
三、算法分析
1.暴力枚举法排序四层for循环set去重时间复杂度O(n^4)-----》这个不可跑过力扣
2.双指针单调性两层for循环时间复杂度O(n^3)-》利用率三数之和--》利用率两数之和
算法步骤 1.排序 2.设置第一个固定数 3.设置第二个固定数 4.两数之和设置两个指针leftright-》降低复杂度的关键 5.细节处理重点关注去重问题 注意事项
去重1.去除第一固定数的重如00求出来的一样
2.去除第二个数的重如第一固定数是-1第二固定数00结果一样
3.去除两数之和的重
四、代码编写 public ListListInteger fourSum(int[] nums, int target) {Arrays.sort(nums);//排序ListListInteger Foursum new ArrayList();for (int i 0; i nums.length; )//固定一个数{for (int j i 1; j nums.length;)//固定第二个数{long tar (long) target - nums[i] - nums[j];//求出两数之和的目标ListInteger list new ArrayList();//两数之和int left j 1;int right nums.length - 1;while (left right) {if (left nums.length nums[left] nums[right] tar) {left;} else if (right 0 nums[left] nums[right] tar) {right--;} else {list.add(nums[i]);list.add(nums[j]);list.add(nums[left]);list.add(nums[right]);Foursum.add(list);//去除第三重while (left nums.length nums[left] list.get(2)) {left;}while (right 0 nums[right] list.get(3)) {right--;}}}//去除第二重j;while (j nums.length nums[j] nums[j - 1]) {j;}}//去除第三重i;while (inums.length nums[i]nums[i-1]){i;}}return Foursum;} 你学废了吗
