求三数之和为零的三元组集合

题目：

思路：

1. 题目要求三数之和为零，即:a+b+c=0; 那么若满足b+c = -a的话就满足题目的第一个要求啦。假设-a = tem 那么 b+c=tem就说明满足条件。这样的话三数之和变成了两数之和，再两个数字和的基础上，只需要找到一个tem为定点以后，然后再判断数组中剩下的数字两两相加是否等于tem即可。若用暴力求解的话会超出时间限制。此时，假设该数组是一个有序数组（升序）的话，那么我们可以知道，从左到右数字时依次增加的。此时设置索引left，mid，right，然后以最左边的点为定点（tem），只需要看nums[mid]+nums[right]+nums[left]?=0即：nums[mid]+nums[right]=-nums[left] ---> nums[mid]+nums[right]=tem。
2. 而且题目中要求不能重复，那么当nums[left]判断后，需要判断之前的nums[left-1]和现在的nums[left]是否是相同的数字，若是的话，left继续往后移动，直到移动到不同的数字为止。同理，mid right也是这样操作。
3. 根据以上两个思路之后，我们知道这个思路是建立在有序数组上的。所以我们首先要将数组进行升序使得为有序数组后再进行之后的操作。

• 其中，我们知道a+b+c=0的话，a+b 要与 c互为相反数，所以定点left只需要在小于等于0之前进行循环就可以。
• 其中，right往小的方向移动，mid往大的方向移动。所以根据num[right]+nums[mid]与tem的对比，来移动它们。
• 若num[right]+nums[mid]<tem 那么说明等于tem的数值范围靠近右边，此时要增大两数之和，mid往右边移动。
• 若num[right]+nums[mid]>tem 那么说明等于tem的数值范围靠近左边，此时要减小两数之和，right往左移动。
  
• 为了减少时间复杂度，可以选择相应的排序算法去实现。

代码实现：

class Solution {
public:
    void sort(vector<int>& nums)
    {
        int temp = 0;
        int len = nums.size();
        for(int i=0; i<len; i++)
        {
            for(int j=i+1; j<len; j++)
            {
                if(nums[i] > nums[j])
                {
                    temp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = temp;

                }
            }
        }
    }
    vector<vector<int> > threeSum(vector<int>& nums)
    {
        int len = nums.size()/3 ;
        vector <int> vi(3);
        vector <vector<int> > arry;
        sort(nums);
        int right;
        int mid;
        for(int left=0; (left<nums.size()&&nums[left]<=0); left++)
        {
            mid = left+1;
            right = nums.size()-1;
            int tem = 0 - nums[left];
            if(left > 0 && nums[left]==nums[left-1])
            {
                continue;
            }
            while(mid < right)
            {
                if(nums[mid] + nums[right] == tem)
                {
                    int m = nums[mid];
                    int r = nums[right];
                    vi[0] = nums[left];
                    vi[1] = nums[mid];
                    vi[2] = nums[right];
                    arry.push_back(vi);
                    while((mid < right) && (nums[++mid]==m))
                    {
                        continue;
                    }
                    while((mid < right) && (nums[--right]==r))
                    {
                        continue;
                    }
                }
                else if(nums[mid] + nums[right] > tem)
                {
                    right--;
                }
                else{
                    mid++;
                }
            }
        }
        return arry;
    }

};