算法题之三数之和问题

算法题之三数之和问题

题目描述

题目分析

方式2:图解

最后得到结果集:

java代码

方式1:dfs遍历

public List<List<Integer>> threeSum(int[] nums) { //首先对nums数组进行排序处理 Arrays.sort(nums); //保存所有的结果集:res List<List<Integer>> res = new ArrayList<>(); //存放每一种结果集:sub List<Integer> sub = new ArrayList<>(); //进行dfs遍历查找 findThreeSum(0,nums,res,sub,0); //将结果集返回 return res; } private void findThreeSum(int start, int[] nums, List<List<Integer>> res, List<Integer> sub,int target) { //若sub的长度为3并且target == 0:则进行判断 if (sub.size() == 3 && target == 0) { if (!res.contains(sub)) { res.add(new ArrayList<>(sub)); } return; } //去重操作:排序以后若sub第一个元素大于0,则后面数字相加结果必然大于0,故直接返回 if (sub.size() > 0 && sub.get(0) > 0) { return; } for (int i = start; i < nums.length; i++) { //sub加入nums[i] sub.add(nums[i]); //递归调用findThreeSum:进行dfs遍历,target = tartget - nums[i],最终sub存满三个数,且target仍然为0,表示相加结果为0 findThreeSum(i + 1,nums,res,sub,target - nums[i]); //回溯时,将sub中的最后一个元素去除(不满足要求或者进行下一种选择) sub.remove(sub.size() - 1); } }

方式2:排序+双指针

public List<List<Integer>> threeSum(int[] nums) { //定义list保存最后的结果集 List<List<Integer>> res = new ArrayList<>(); //定义len:nums数组的长度 int len = nums.length; if(nums == null || len < 3) { //则表示数组nums不满足要求,直接返回res:即空的集合 return res; } Arrays.sort(nums); //遍历排序以后的nums数组 for (int i = 0; i < len; i++) { if (nums[i] > 0) { //nums[i]大于0:则由于nums数组进行从小到大的排序,故后面的两个数加上nums[i]结果必然大于0 break; } if(i > 0 && nums[i] == nums[i-1]) { continue;//由于两者作为三个数的第一个数相同,直接去重[结果存在重复性] } //分别定义左指针和右指针 int left = i + 1; int right = len - 1; //while循环条件left < right while (left < right) { //求和 int sum = nums[i] + nums[left] + nums[right]; if (sum == 0) { //将其加入结果集当中 res.add(Arrays.asList(nums[i],nums[left],nums[right])); //进行左右指针遍历去重工作 while (left < right && nums[left] == nums[left + 1]) {left++;}//左去重 while (left < right && nums[right] == nums[right - 1]) {right--;}//右去重 //然后分别将左指针右移,右指针左移,进行下一次的判断 left++; right--; //若是sum<0,则表示左指针指向的值数值少了,则将左指针右移 }else if (sum < 0) { left++; //若是sum>0,则表示右指针指向的值数值多了,则将右指针左移 }else if (sum > 0) { right--; } } } //整个for循环结束,即找到了所有的不重复的组合 return res; }