题目描述
给你一个整数数组 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] <= 105
解法一
思路：
hashmap记录出现的整数以及出现的次数，set集合对输入的数组进行去重后再转化为list方便进行随机读取。3个位置，从list中读取第一个位置的数，再读取第二个数，并将两个数的可用次数再hashmap中减一，看看hashmap是否存在满足要求的第三个数，没有则第二个数换一个，有则判断这个数是否可用，满足要求进入答案。之后所有答案可能出现重复，利用set再进行一次去重。
代码：
import java.util.Arrays;
import java.util.Scanner;
import java.util.*;
import java.util.stream.Collectors;public class leetcode_006 {public static List<List<Integer>> threeSum(int[] nums) {//记录所有的结果List<List<Integer>> res = new ArrayList<>();//一个set记录所有可以出现的元素，hashmap记录元素和元素出现的次数Set<Integer> set = new HashSet<>();Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {set.add(nums[i]);if(!map.containsKey(nums[i])) {map.put(nums[i], 1);}else {map.put(nums[i], map.get(nums[i]) + 1);}}//将数字集合转化为list,方便进行随机读取List<Integer> numList = set.stream().sorted().collect(Collectors.toList());//利用字符串的集合进行去重Set<String> set_string = new HashSet<>();for(int i = 0; i < numList.size(); i++) {if(map.get(numList.get(i)) == 0)continue;//拿到索引为i的这个数，这个数的个数减1map.put(numList.get(i), map.get(numList.get(i)) - 1);for (int j = 0; j < numList.size(); j++) {//拿到索引为j的这个数，这个数的个数减1if(map.get(numList.get(j)) == 0)continue;map.put(numList.get(j), map.get(numList.get(j)) - 1);//第三个数int third = 0 - numList.get(i) - numList.get(j);//判断这个数是否存在if (map.containsKey(third) && map.get(third) > 0) {//这个三个数可以组成一个结果int[] num_temp=Arrays.asList(numList.get(i), numList.get(j), third).stream().mapToInt(Integer::valueOf).toArray();Arrays.sort(num_temp);String num_string=Arrays.toString(num_temp);set_string.add(num_string.substring(1, num_string.length() - 1));}//返回前要把j补回map.put(numList.get(j), map.get(numList.get(j)) + 1);}map.put(numList.get(i), map.get(numList.get(i)) + 1);}//将结果转化为listfor(String num : set_string) {List<Integer> list=Arrays.stream(num.split(",")).map(String::trim).map(Integer::parseInt).collect(Collectors.toList());res.add(list);}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String[] line = sc.nextLine().split(",");int[] nums= Arrays.stream(line).mapToInt(Integer::parseInt).toArray();List<List<Integer>> result =threeSum(nums);for(List<Integer> list:result){System.out.println(list);}}
}
解法二
思路：
来自官方的解答，首先对数组进行排序，我们枚举的三元组 (a,b,c) 满足 a≤b≤c，保证了只有 (a,b,c) 这个顺序会被枚举到，而 (b,a,c)、(c,b,a) 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。
同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复。继续优化的，可以发现，如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a+b+c=0。当第二重循环往后枚举一个元素 b′ 时，由于 b′>b，那么满足 a+b′+c′=0 的 c′ 一定有 c′<c，即 c′ 在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。
有了这样的发现，我们就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针
代码：
import java.util.Arrays;
import java.util.Scanner;
import java.util.*;public class leetcode_006 {public static List<List<Integer>> threeSum(int[] nums) {int n = nums.length;Arrays.sort(nums);List<List<Integer>> ans = new ArrayList<List<Integer>>();// 枚举 afor (int first = 0; first < n; ++first) {// 需要和上一次枚举的数不相同if (first > 0 && nums[first] == nums[first - 1]) {continue;}// c 对应的指针初始指向数组的最右端int third = n - 1;int target = -nums[first];// 枚举 bfor (int second = first + 1; second < n; ++second) {// 需要和上一次枚举的数不相同if (second > first + 1 && nums[second] == nums[second - 1]) {continue;}// 需要保证 b 的指针在 c 的指针的左侧while (second < third && nums[second] + nums[third] > target) {--third;}// 如果指针重合，随着 b 后续的增加// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环if (second == third) {break;}if (nums[second] + nums[third] == target) {List<Integer> list = new ArrayList<Integer>();list.add(nums[first]);list.add(nums[second]);list.add(nums[third]);ans.add(list);}}}return ans;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String[] line = sc.nextLine().split(",");int[] nums= Arrays.stream(line).mapToInt(Integer::parseInt).toArray();List<List<Integer>> result =threeSum(nums);for(List<Integer> list:result){System.out.println(list);}}
}