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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

//cpp
/*
3SUM:
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? 
Find all unique triplets in the array which gives the sum of zero.
*/

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int length = nums.size();
        vector<vector<int>> result;

        //对数组nums进行快速排序
        sort(nums.begin(), nums.end());

        if(length > 0 && nums[length-1] < 0) return result; 

        for (int i = 0; i < length - 1; i++) 
        {
            // if nums[i] > 0, we can never get sum to 0
            if(nums[i] > 0) break;
            
            //avoid duplicate triplets
            if (i != 0 && nums[i] == nums[i - 1]) continue;
            
            int target = -nums[i];
            int left = i + 1, right = length - 1;
            // both side
            while (left < right) 
            {
                // target is negative
                if (nums[left] + nums[right] > target)
                {
                    // right side is too huge
                    right--;
                } 
                else if (nums[left] + nums[right] < target) 
                {
                    // left side is too small
                    left++;
                }
                else 
                {
                    result.push_back({nums[i],nums[left],nums[right]});
                    while (++left < right && nums[left] == nums[left - 1]) ;
                    while (--right > left && nums[right] == nums[right + 1]) ;
                }
            }
        }
        return result;
    }
};

#python
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if len(nums) < 3:
            return []
        nums.sort()
        res = set()
        for i, v in enumerate(nums[:-2]):
            if i >= 1 and v == nums[i-1]:
                continue
            d = {}
            for x in nums[i+1:]:
                if x not in d:
                    d[-v-x] = 1  #因为排序的原因，a<=b<=c，c=-(a+b)一定在a/b后面；d[-v-x]就是寻找c。
                else:
                    res.add((v, -v-x, x))
        return list(map(list, res))

#python更加详细解释
class Solution(object):
    def threeSum(self, nums):
        nums.sort()
        res = []
        for idx,val in enumerate(nums):
            if idx>=1 and val == nums[idx-1]:
                continue
            # 思想：有没有人正在找我？没有的话，我就去找我想找的人。
            wanted_pairs = {} # 想找的人
            temp=None
            for pair in nums[idx+1:]:
                if pair==temp:
                    continue
                if pair not in wanted_pairs: # Not他们想找的人,then加入他们去找我想找的人
                    wanted_pairs[0 - val - pair]=1
                else:
                    res.append([val,pair,0 - val - pair]) # 我就是他们中那个谁想找的人
                    temp=pair
        return res