题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例1

  1. 输入：nums = [-1,0,1,2,-1,-4]
  2. 输出：[[-1,-1,2],[-1,0,1]]

示例2

输入：nums = [0]
输出：[]

实现

思路1 暴力搜索

利用三重循环对三个数字分别遍历求和。最后使用hashmap去重，得到最终不含重复三元组的答案。

时间复杂度：15. 三数之和 - 图1

思路2 排序+双指针

首先题目要求不可以包含重复的答案，所以可以先对数组进行一次排序，使数组按从小到大排列。这样我们在遍历数组的时候，枚举的三元组(a,b,c)就会满足15. 三数之和 - 图2，而不会出现(b,a,c)这样的三元组，减少了重复。同时对每一重循环，相邻两次枚举的元素不能相同，否则也会重复。
不过如果只是上述改进，这题时间复杂度还是（三重循环）。这里可以想到，三数之和如果在遍历时确定了第一个数，那么剩下两个数的和也就确定了(0-第一个数），而这个就是Leetcode第一题“两数之和”，可以用双指针的方法，将遍历第二、第三个数的2个循环，变为保持第二重循环不变（第二个数字还是从小到大枚举），而将第三重循环变成一个从数组最右端往左移动的指针。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());

        int n = nums.size();
        // 枚举第一个数a
        for(int a = 0; a < n; a++){
            // 每一重循环枚举的元素不能相同
            if(a > 0 && nums[a] == nums[a-1]){
                continue;
            }

            // 第三个数c的指针初始化在最右端
            int c = n-1;
            int target = 0 - nums[a];

            // 第二重循环枚举第二个数b
            for(int b = a+1; b < n; b++){
                // 每一重循环枚举的元素不能相同
                if(b>a+1 && nums[b] == nums[b-1]){
                    continue;
                }
                // 移动右指针，直到bc重合。解决twosum问题
                while(b < c && nums[b]+nums[c] > target) { // 如果b+c<target，不需要遍历了
                    c--;
                }
                // 如果b,c指针重合，由上面已知b+c>target，而第二重循环会使b增大，所以依然有b+c>target
                if(b == c){
                    break;
                }
                if(nums[b]+nums[c] == target){
                    ans.push_back({nums[a], nums[b], nums[c]});
                }

            }
        }
        return ans;
    }
};

时间复杂度：，其中N时数组nums的长度。
空间复杂度：15. 三数之和 - 图3。这里忽略了存储答案的ans空间，只考虑额外的排序的空间复杂度为15. 三数之和 - 图4（排序修改了输入数组nums）。