题目描述
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
样例
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = []
输出：[]
示例 3：
输入：nums = [0]
输出：[]
题目评估
知识点：数组、双指针、排序
官方难度：中等
分析
一搭眼的方法就是三重循环暴力，但是会有重复。排序后可以方便跳过重复。
nums[a] + nums[b] + nums[c] = 0，当 nums[a] 不变的时候，nums[b] 越大，nums[c] 必须越小才能使等式继续有可能等于 0，所以当 a 指针固定时 b 指针向右移的情况下 c 指针指向的数字必须越来越小。故当 a 指针不动，时 b 和 c 组成双指针，从 a + 1 到 nums.length - 1 之间向中间移动，当 b 和 c 指针重合便可以开始下一轮第一重循环。
Java代码题解
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
// 排序
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
// 第一个数字去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1, k = nums.length - 1; j < nums.length; j++) {
// 第二个数去重
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// 保证第二个指针在第三个指针左边的情况下，结果不符就左移第三指针使第三个数字变小
while (j < k && nums[i] + nums[j] + nums[k] > 0) {
k--;
}
// 指针重合跳出
if (j >= k) {
break;
}
// 如果相加等于0放入结果集
if (nums[i] + nums[j] + nums[k] == 0) {
List<Integer> current = new ArrayList<>();
current.add(nums[i]);
current.add(nums[j]);
current.add(nums[k]);
res.add(current);
}
}
}
return res;
}
}
复杂度分析
时间复杂度：O(N^2)，其中 N 是数组 nums 的长度。
空间复杂度：O(logN)。我们忽略存储答案的空间，额外的排序的空间复杂度为 O(logN)。然而我们修改了输入的数组 nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序，空间复杂度为 O(N)。