文章收录于LeetCode专栏
三数之和
给你一个包含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]
输出：[]
题解
第一步审题，给定一个数组请求其中任意不重复三个元素之和为0，题意很简单就是任意从数组中取三个元素相加要等于0，且求出所有不重复的组合。
第二步列出所有解，首先可以使用暴力三层枚举求解，其次在两数之和基础之上使用一个hash表来换取少一层循环，最后可以使用双指针左右夹逼法来求解。
解法一（暴力枚举）
所谓暴力枚举就是采用三层循环，每层循环取出数组中一个元素，判断三层循环取出的三个元素相加是否等于0，因为要求不包含重复的三元组，所以在判断的过程中必须要进行一次判重。
class Solution{
public List<List<Integer>> threeSum(int[] nums){
if(nums.length == 0){
return Collections.emptyList();
}
Set<List<Integer>> res = new HashSet<>();
for(int i=0; i<nums.length-2; i++){
for(int j=i+1; j<nums.length-1; j++){
for(int k=j+1; k<nums.length; k++){
if(nums[i] + nums[j] + nums[k] == 0){
List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
Collections.sort(list);
res.add(list);
}
}
}
}
return new ArrayList(res);
}
}
解法二（hash表）
在求解两数之和的时候使用空间换时间的方式，采用hash表来记录遍历到的元素，从而可以用于下次判断的时候使用，同样三数之和也可以使用hash表来记录一层元素，使其退化为两数之和，只是这里的目标值每次都不一样而已，同样需要对结果进行判重操作。
class Solution{
public List<List<Integer>> threeSum(int[] nums){
if(nums.length == 0){
return Collections.emptyList();
}
Set<List<Integer>> res = new HashSet<>();
for(int i=0; i<nums.length-1; i++){
int target = 0 - nums[i];
Map<Integer, Integer> map = new HashMap<>();
for(int j=i+1; j<nums.length; j++){
int sub = target - nums[j];
if(Objects.nonNull(map.get(sub))){
List<Integer> list = Arrays.asList(nums[j], sub, nums[i]);
Collections.sort(list);
res.add(list);
}
map.put(nums[j], j);
}
}
return new ArrayList(res);
}
}
解法三（左右指针夹逼）
以上两种解法因为它们消耗的时间都太高，所以表现都不尽人意。题目中没有要求元素下标，所以我们完全可以先将数组进行从小到大排序，这样一来我们就可以从左开始每次固定一个元素，再使用左右两个指针来移动获取剩下的两个元素，如果当前三数之和小于0，则说明左指针应该向右移动（已经对数组进行排序，右边元素大于左边元素）；如果当前三数之和大于0，则说明右指针应该向左移动；等于0则说明找到匹配元组。
class Solution{
public List<List<Integer>> threeSum(int[] nums){
if(nums.length == 0){
return Collections.emptyList();
}
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for(int i=0; i<nums.length-2; i++){
if(nums[i] > 0){
// 当元素大于0，说明以后元素都大于0，三数之和不可能再为0
break;
}
if(i > 0 && nums[i] == nums[i-1]){
// 跳过重复元素
continue;
}
// 左指针
int j = i + 1;
// 右指针
int k = nums.length -1;
while(j < k){
int sum = nums[i] + nums[j] + nums[k];
if(sum == 0){
res.add(Arrays.asList(nums[i], nums[j], nums[k]));
// 跳过重复元素
while(j < k && nums[j] == nums[++j]);
// 跳过重复元素
while(j < k && nums[k] == nums[--k]);
}
if(sum < 0){
// 三数之和小于0，左指针向右移动
// nums[j] == nums[++j] 移动且跳过重复元素
while(j < k && nums[j] == nums[++j]);
}
if(sum > 0){
// 三数之和大于0，右指针向左移动
// nums[k] == nums[--k] 移动且跳过重复元素
while(j < k && nums[k] == nums[--k]);
}
}
}
return res;
}
}
第三步分析时间复杂度和空间复杂度，暴力枚举法使用了三层循环且没有使用额外的内存空间，所以时间复杂度为O(n3)，空间复杂度为O(1)；hash表使用空间换时间的方法，所以时间复杂度为O(n2)，空间复杂度为O(n)；左右指针夹逼同样使用了两层循环所以时间复杂度为O(n2)，但是没有使用额外的内存空间所以空间复杂度为O(n)。