（每日一练C++）CC134 三数之和

古城微笑少年丶 2023-10-04 17:54 2阅读 0赞

### 描述 ###

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

数据范围：0 \\le n \\le 30000≤n≤3000，数组中各个元素值满足 |val | \\le 100∣val∣≤100

空间复杂度：O(n^2)O(n2)，时间复杂度 O(n^2)O(n2)

注意：

1.  三元组（a、b、c）中的元素可以按任意顺序排列。
2.  解集中不能包含重复的三元组。

### 示例1 ###

输入：

[-10,0,10,20,-10,-40]

复制返回值：

[[-10,-10,20],[-10,0,10]]

复制

### 示例2 ###

输入：

[-2,0,1,1,2]

复制返回值：

[[-2,0,2],[-2,1,1]]

复制

### 示例3 ###

输入：

[0,0]

复制返回值：

[]

/**
     * （1）首先对数组进行排序（从小到大）
     * （2）依次取出第 i 个数（i从0开始），并且不重复的选取（跳过重复的数）
     * （3）这样问题就转换为 2 个数求和的问题（可以用双指针解决方法）
     *  2 数求和问题
     * 	   （4）定义两个指针：左指针（left） 和 右指针（right）
     * 	   （5）找出固定 left， 此时left所指的位置为数组中最小数，再找到两个数和 不大于 target 的最大 right 的位置
     * 	   （6）调整 left 的位置（后移），求解和是否为 target O(n)
     *     （7）时间复杂度：O(nlogn) + O(n)
    */
    class Solution {
    public:
        vector<vector<int> > threeSum(vector<int> &num) {
            //数组排序（小-->大）
            sort(num.begin(), num.end());
            //结果集合
            vector<vector<int>> ans;
            
            //先依次取出一个数，转换为 2 数求和问题
            for (int i = 0; i < num.size(); i++){
                if ( i == 0 || num[i] != num[i-1]){//防止重复
                    //定义左右指针
                    int left = i + 1, right = num.size() - 1;
                    // 2 数求和问题，固定left， 找出最大的right
                    while (left < right){
                        //right 左移， 减小 num[right] 的值
                        while (left < right && num[i] + num[left] + num[right] > 0) right --;
                        if (left < right && num[i] + num[left] + num[right] == 0){
                            //保存当前结果
                            vector<int> temp(3);
                            temp[0] = num[i];
                            temp[1] = num[left];
                            temp[2] = num[right];
                            //保存到最终的结果中
                            ans.push_back(temp);
                            //右移 left （去除重复）
                            while (left < right && num[left] == temp[1]) left ++;
                        } else { // num[i] + num[left] + num[right] < 0的情况，left右移，增大num[left]的值
                            left++;
                        }
                    }
                }
            }
            return ans;
        }
    };