题解 | #牛牛的三元组问题#

1.考察知识点

数组、双指针

2.编程语言

C++

3.解题思路

该题为三数之和问题，针对三数之和问题，首先将数组进行排序；

然后，使用双指针方法，分别定义i，j，k三个指针，分别指向3个数字

按照数组顺序取第一个数字位置为i，第二个数字从i+1位置向后寻找，第三个数字从末尾向前遍历寻找

共有三种情况nums[i]+nums[j]+nums[k]==0，直接将i,j,k添加到返回数组中

nums[i]+nums[j]+nums[k]>0，k--

nums[i]+nums[j]+nums[k]<0，j--

分析重复情况，实现去重操作。

当i>0 && nums[i]==nums[i-1]时，跳过nums[i]

当k<n-1 && nums[k]==nums[k+1]时，跳过nums[k], k-1以后继续进行遍历

4.完整代码

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > findTriplets(vector<int>& nums) {
        vector<vector<int>> res;
        // write code here
        int n = nums.size();
        sort(nums.begin(),nums.end());
        //取第一个数字
        for(int i=0;i<n-2;i++)
        {
            //去除重复的第一个元素
            if(i>0 && nums[i]==nums[i-1])
            {
                continue;
            }
            //第二个元素每次从i+1向后寻找
            int j = i+1;
            //第三个元素从n-1向前寻找
            int k = n-1;
            //结束条件
            while(j<k)
            {
                
                //去除重复的元素
                if(k<n-1 && nums[k]==nums[k+1])
                {
                    k--;
                    continue;
                }
                //找到以后添加到res二维数组中
                if(nums[i]+nums[j]+nums[k]==0)
                {
                    vector<int> tmp;
                    tmp.push_back(nums[i]);
                    tmp.push_back(nums[j]);
                    tmp.push_back(nums[k]);
                    res.push_back(tmp);
                    j++;
                    k--;
                }
                //如果和大于0，最大值减小
                if (nums[i]+nums[j]+nums[k]>0){
                    k--;
                }
                //如果和小于0，最小值增大
                if (nums[i]+nums[j]+nums[k]<0){
                    j++;
                }
            }
        }
        return res;  
    }
};