LeetCode刷题之旅（10）--三数之和（中等题）

每天属于自己的时间，就是慢慢的刷题的时候，啥也不用想，沉浸在写出最佳程序的过程中，沉浸在自己阅读大牛代码，提升自我的过程中，那种满足感，真的很让人享受<.>

题目:三数之和

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

注意：答案中不可以包含重复的三元组。

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

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

解题思路：

思路有两种，一种是先排序，然后找到三元素，最后去重，难点是如何记录和去除重复的，此方法比较麻烦，所以放弃。
第二种就是,先排序，然后固定一个值，接着用双指针的思想去找到相加为0的三元素，期间，遇到有重复的跳过即可。

```c++
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        if(nums.size()<3)return res;
        sort(nums.begin(),nums.end());
        
        for(int mid=0;mid<=nums.size()-1;mid++)
        {
            if(nums[mid]>0)break;
            if(mid>0&&nums[mid]==nums[mid-1])continue;
            int l=mid+1,r=nums.size()-1;
            while(l<r)
            {
                if(nums[l]+nums[mid]+nums[r]==0)
                {
                    if(l==mid+1||r==nums.size()-1)
                    {
                        res.push_back(vector<int>{nums[l], nums[mid], nums[r]});
                        l++;
                        r--;
                    }
                    else{
                        if(nums[l]==nums[l-1])
                        {
                            l++;
                        }
                        else{
                            if(nums[r]==nums[r+1])
                            {
                                r--;
                            }
                            else
                            {
                                res.push_back(vector<int>{nums[l], nums[mid], nums[r]});
                                l++;
                                r--;
                            }
                        }
                    }
                }
                else
                {
                    if(nums[l]+nums[mid]+nums[r]<0)
                    {
                        l++;
                    }
                    else
                    {
                        r--;
                    }
                }
            }
            
        }
        
        return res; 
    }
        
        
};
执行用时：140 ms