题目:
15. 三数之和 - 力扣(LeetCode)15. 三数之和 - 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意:答案中不可以包含重复的三元组。 示例 1:输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]解释:nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。注意,输出的顺序和三元组的顺序并不重要。示例 2:输入:nums = [0,1,1]输出:[]解释:唯一可能的三元组和不为 0 。示例 3:输入:nums = [0,0,0]输出:[[0,0,0]]解释:唯一可能的三元组和为 0 。 提示: * 3 <= nums.length <= 3000 * -105 <= nums[i] <= 105http://link.dataword.cloud/1AwrSv
总结:
这个题还是比较难的,三数之和,两数之和,看着差不多,但是要求呀这些还是很有差距的。题目描述就不多赘婿了。大家点击我的短链接就能跳过去。
这个题的解法就是排序完,利用递归并定住一个数据,将三数之和变成,两数之和,然后递归找解。
代码示例:
public static List<List<Integer>> threeSum2(int[] nums){Arrays.sort(nums);List<List<Integer>> result = new LinkedList<>();dfs2(3, 0, nums.length - 1, 0, nums,new LinkedList<>(), result);return result;}public static void dfs2(int n//用来控制 递归的结束条件(找到结果有n 个数),int i//左边界,int j//右边界,int target//目标值,int[] nums,//数组LinkedList<Integer> stack,//固定的数List<List<Integer>> result//结果){if(n == 2){//递归结束标志。就剩两个数据就没必要继续了twoSum2(i, j, nums, target, stack, result);return ;}for (int k = i; k < j; k++) {if(k>i && nums[k] == nums[k-1]){ //检查 k 的有效边界,以及检查重复continue;}//固定一个数据stack.push(nums[k]);dfs2(n-1,k+1,j,target - nums[k],nums,stack,result);//弹出固定的方法stack.pop();}}//找解的核心方法static public void twoSum2(int i, int j, int[] nums, int target,LinkedList<Integer> stack,List<List<Integer>> result) {while(i<j){//保持边界int sum = nums[i]+nums[j];//调整边界if(sum < target){i++;} else if (sum > target) {j--;}else {//找到解ArrayList<Integer> list = new ArrayList<>(stack);list.add(nums[i]);list.add(nums[j]);result.add(list);//继续找(调整边界)i++;j--;//这两个是在找重复的,自己和自己前一个重复就跳走,重复没意义while (i < j && nums[i] == nums[i - 1]) {i++;}while (i < j && nums[j] == nums[j + 1]) {j--;}}}}
视频讲解:
进阶数据结构和算法-332-三数之和-Leetcode15_哔哩哔哩_bilibili进阶数据结构和算法-332-三数之和-Leetcode15是大厂必备数据结构与算法Java视频教程(下篇),java高级程序员必学的数据结构与算法的第178集视频,该合集共计200集,视频收藏或关注UP主,及时了解更多相关视频内容。http://link.dataword.cloud/3qCztX黑马讲解的很透彻,建议看看,💪