8.【LeetCode 18】四数之和 —— Java 排序 + 双指针解法详解

目录1. 题目解析18. 四数之和​示例 1示例 22. 算法原理解法一排序 暴力枚举 利用 set 去重解法二排序 双指针处理细节问题3. 编写代码OJ链接https://leetcode.cn/problems/4sum/description/1. 题目解析18. 四数之和​难度中等给你一个由 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]]2. 算法原理解法一排序 暴力枚举 利用 set 去重解法二排序 双指针依次固定一个数a在a后面的区间内利用“三数之和”找到三个数使这三个数的和等于target - a即可。进一步细化1. 依次固定一个数 b; 2. 在 b 后面的区间内利用“双指针”找到两个数 使这两个数的和等于 target - a - b 即可。处理细节问题不重不漏3. 编写代码class Solution { public ListListInteger fourSum(int[] nums, int target) { ListListInteger ret new ArrayList(); //排序 Arrays.sort(nums); //四数之和 int n nums.length; for(int i 0; i n - 3; ){//固定i //三数之和 for(int j i 1; j n - 2; ){//固定j //两數之和 int left j 1, right n - 1; //避免溢出这里需要使用Long long aim (long)target - nums[i] - nums[j]; while(left right){ int sum nums[left] nums[right]; if(sum aim) right--; else if(sum aim) left; else{ ret.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--; } } //去重二 j; while(j n nums[j] nums[j - 1]) j; } //去重三 i; while(i n nums[i] nums[i - 1]) i; } return ret; } }