本文主要是介绍leetcode15-3Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
给你一个整数数组 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] 。
注意，输出的顺序和三元组的顺序并不重要。
分析
可以想一想2Sum的解法，所以我们整体的思路就是固定一个元素，然后求剩下的元素当中哪俩个元素的和满足（0-固定的这个元素）的大小。同时我们可以有一些优化的地方，我们在排序以后固定元素的时候如果发现元素比0大，这种可以直接break了，因为比0大的元素不可能再和其它元素相加等于0，然后如果上一个元素和当前元素相同的这种重复场景也可以忽略
最终由于list需要唯一，可以借助set来实现
import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;public class threeSum {public static void main(String[] args) {int[] arr = {-1,0,1,2,-1,-4};List<List<Integer>> lis = getLis(arr);for(List<Integer> li : lis) {li.stream().forEach(System.out::println);System.out.println();}}public static List<List<Integer>> getLis(int[] nums) {int len = nums.length;Arrays.sort(nums);Set<List<Integer>> set = new HashSet();for(int i = 0;i<len-2;i++) {if(nums[i] > 0) {break;}if(i > 0 && nums[i-1] == nums[i]) {continue;}int j = i+1;int k = len - 1;int target = 0 - nums[i];while(j<k) {if(nums[j] + nums[k] == target) {List<Integer> lis = new ArrayList();lis.add(nums[i]);lis.add(nums[j]);lis.add(nums[k]);j++;k--;set.add(lis);} else if(nums[j]+nums[k] < target) {j++;} else {k--;}}}List<List<Integer>> res = new ArrayList();res.addAll(set);return res;}
}
这篇关于leetcode15-3Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
