# 15. 三数之和

## 问题

给你一个整数数组nums，判断是否存在三元组 [nums[i], nums[j], nums[k]]满足i!=j、i!=k 且 j!=k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

例子1：

```java
输入：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] 。
注意，输出的顺序和三元组的顺序并不重要。
```

## 思路

对于该问题，最简单的方法是暴力法，时间复杂度为O(n^3)。但是暴力法也有一个问题，即结果的去重问题，例子1中有两个[-1]，因此会有至少两个重复解：

- [-1, 0 ,1]

解决该问题的常见方法是哈希表，然而该方法的缺点如下：

1. 耗费空间
2. 对于复杂数据结构不方便构建哈希表

因此，本题利用了另一种去重方法，排序。

对于该问题，例如：

[-1, -1, 0, 2, 1]

对于该例子，针对第一个-1，如果我们遍历过了所有三数之和的情况，那么第二个-1则不需要处理了。

那么接下来就将问题的去重部分简化了，但是如何合理的查找所有的序列呢？例如对于第一个-1，难道要对[-1,0,2,1]这个子数组进行O(n^2)的遍历么？其实这里还有重复的问题，我们需要寻找另一个排序方式去重。

这里我们构建一个递增序列：

1. 记我们当前正在处理的三元组中第一个值S[0]的index = i，因此，S[1]和S[2]的值从[i+1 :]子数组中取出
2. 注意[i+1 :]子数组已经进行了从小到大的排序
3. 取Left = i + 1, Right = n - 1(n 为输入数组长度)，
   1. 如果nums[Left]+nums[Right]+nums[i] > 0，证明nums[Left]+nums[Right]过大，只需要Right -- 就保证了该值递减
   2. 如果nums[Left]+nums[Right]+nums[i] < 0，证明nums[Left]+nums[Right]过小，只需要Left ++ 就保证了该值递增
   3. 如果遇到了重复值，只需要处理第一个值，其余的跳过即可



## 代码实现

```go

import "sort"

func threeSum(nums []int) [][]int {
	result := [][]int{}
    // 排序
	sort.Ints(nums)
	for i := 0; i < len(nums)-2; i++ {
		// 外部去重
        if i-1 >= 0 && nums[i-1] == nums[i] {
			continue
		}
		sum := -nums[i]
		left := i + 1
		right := len(nums) - 1
		for left < right {
			temp := nums[left] + nums[right]
			if temp == sum {
				result = append(result, []int{nums[i], nums[left], nums[right]})
				// 内部去重
                for left < right && nums[left] == nums[left+1] {
					left++
				}
                // 内部去重
				for left < right && nums[right] == nums[right-1] {
					right--
				}
				left++
				right--
			} else if temp > sum {
				right--
			} else {
				left++
			}
		}
	}
	return result
}
```
我的c++算法流程：
特判，对于数组长度 nnn，如果数组为 nullnullnull 或者数组长度小于 333，返回 [][][]。
对数组进行排序。
遍历排序后数组：
若 nums[i]>0nums[i]>0nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 000，直接返回结果。
对于重复元素：跳过，避免出现重复解
令左指针 L=i+1L=i+1L=i+1，右指针 R=n−1R=n-1R=n−1，当 L<RL<RL<R 时，执行循环：
当 nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,RL,RL,R 移到下一位置，寻找新的解
若和大于 000，说明 nums[R]nums[R]nums[R] 太大，RRR 左移
若和小于 000，说明 nums[L]nums[L]nums[L] 太小，LLL 右移

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        // vector<int> tem; 
        sort(nums.begin(),nums.end());
        int pre=0;
        int end=nums.size()-1;
        if(nums[0]>0)  return res;
        if(nums[end]<0)return res;
        
        for(int i=0;i<nums.size();i++)
        {
            pre=i+1;
            end=nums.size()-1;   
            if(i!=0&&nums[i]==nums[i-1])continue;
            
            while(pre<end)
            {	
                if(nums[pre]+nums[end]+nums[i]==0)
                {
                    vector<int> tem{nums[i],nums[pre],nums[end]};
                    res.push_back(tem);
                    do{
                    pre++;
                    end--;}
                  while(pre<end&&nums[pre-1]==nums[pre]&&nums[end+1]==nums[end]);
                }
                if(nums[pre]+nums[end]+nums[i]<0)pre+=1;
                if(nums[pre]+nums[end]+nums[i]>0)end-=1;

            }
        }
        return res;
    }
};
ps:1.注意初始的边界条件i!=0&&nums[i]==nums[i-1]，在i第二次迭代开始判断
2.内部去重，（pre<end&&nums[pre-1]==nums[pre]&&nums[end+1]==nums[end]）
满足pre<end的同时判断满足目标的下一个是否重复。