1 题目
给出一个有 n 个整数的数组 S，在 S 中找到三个整数 a, b, c，找到所有使得 a + b + c = 0 的三元组。
在三元组 (a, b, c)，要求 a≤b≤c。结果不能包含重复的三元组。数组可能包含重复元素，但同一个索引下标的元素不可重复使用
样例 1：
输入：
numbers = [2,7,11,15]输出：
[]解释：找不到三元组使得三个数和为0。
样例 2：
输入：
numbers = [-1,0,1,2,-1,-4]输出：
[[-1, 0, 1],[-1, -1, 2]]解释：[-1, 0, 1]和[-1, -1, 2]是符合条件的2个三元组。
2 解答
我写了一个：
public class Solution { /** * @param numbers: Give an array numbers of n integer * @return: Find all unique triplets in the array which gives the sum of zero. * we will sort your return value in output */ public List<List<Integer>> threeSum(int[] numbers) { // write your code here List<List<Integer>> res = new ArrayList<>(); // 1、当数组为空或者长度为0时，直接返回 if (numbers == null || numbers.length <= 0) { return res; } // 放进 Map 用于快速判断元素是否存在 Map<Integer, Set<Integer>> numMap = new HashMap<>(); for (int i=0; i<numbers.length; i++) { numMap.computeIfAbsent(numbers[i], k->new HashSet<>()) .add(i); } // 三元组结果去重 Set<String> resultRepeat = new HashSet<>(); // 2、遍历 for (int i=0; i<numbers.length; i++) { // 第一个数 int oneNum = numbers[i]; for (int j=0; j<numbers.length; j++) { // 等于下标i的略过 if (j == i) continue; // 第二个数 int twoNum = numbers[j]; // 求差得到第三个数 int minus = 0 - oneNum - twoNum; // 判断第三个数是否存在，存在那么就是一种结果了 Set<Integer> threeIndexSet = numMap.getOrDefault(minus, Collections.EMPTY_SET); if (threeIndexSet == null) continue; // 第三个数的下标集合 for (int threeIndex : threeIndexSet) { // 下标等于i,j的直接略过 if (threeIndex == i || threeIndex == j) continue; // 有结果 List<Integer> oneRes = new ArrayList(3); oneRes.add(oneNum); oneRes.add(twoNum); oneRes.add(minus); // 排序后，校验去重 oneRes.sort(Integer::compareTo); String numStr = String.format("%s%s%S", oneRes.get(0), oneRes.get(1), oneRes.get(2)); if (resultRepeat.contains(numStr)) continue; // 添加进结果 res.add(oneRes); resultRepeat.add(numStr); } } } return res; } }
有点 n^2 的复杂度，感觉还有上升的空间，我再想想。