精选力扣500题第9题 LeetCode 15. 三数之和【c++详细题解】

末蓝、 2021-07-24 18:19 361阅读 0赞

### 目录 ###

*   *   *  1、题目
         *  2、思路
         *  3、代码

### 1、题目 ###

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

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

**示例 1：**

输入：nums = [-1,0,1,2,-1,-4]
    输出：[[-1,-1,2],[-1,0,1]]

**示例 2：**

输入：nums = []
    输出：[]

**示例 3：**

输入：nums = [0]
    输出：[]

**提示：**

*  `0 <= nums.length <= 3000`
 *  `-105 <= nums[i] <= 105`

### 2、思路 ###

**(排序 + 双指针）**  O ( n 2 ) O(n^2) O(n2)

*  1、将整个`nums`数组按从小到大排好序
 *  2、枚举每个数，表示该数`nums[i]`已被确定，在排序后的情况下，通过双指针`l`，`r`分别从左边`l = i + 1`和右边`r = n - 1`往中间靠拢，找到`nums[i] + nums[l] + nums[r] == 0`的所有符合条件的搭配
 *  3、在找符合条件搭配的过程中，假设`sum = nums[i] + nums[l] + nums[r]`  
    若`sum > 0`，则`r`往左走，使`sum`变小  
    若`sum < 0`，则`l`往右走，使`sum`变大  
    若`sum == 0`，则表示找到了与`nums[i]`搭配的组合`nums[l]`和`nums[r]`，存到`ans`中
 *  4、判重处理  
    确定好`nums[i]`时，`l`需要从`i + 1`开始  
    当`nums[i] == nums[i - 1]`，表示当前确定好的数与上一个一样，需要直接跳过  
    当找符合条件搭配时，即`sum == 0`,需要对相同的`nums[l]`和`nums[r]`进行判重出来

### 3、代码 ###

class Solution { 
    public:
        vector<vector<int>> threeSum(vector<int>& nums) { 
            vector<vector<int>> res;
            sort(nums.begin(), nums.end());
            for (int st = 0; st < nums.size(); st++) { 
                while (st != 0  && st < nums.size() && nums[st] == nums[st - 1])
                    st++;
                int l = st + 1, r = nums.size() - 1;
                while (l < r) { 
                    if (nums[st] + nums[l] + nums[r] == 0) { 
                        res.push_back({ nums[st], nums[l], nums[r]});
                        do {  l++; }while (l < r && nums[l - 1] == nums[l]);
                        do {  r--; }while (l < r && nums[r] == nums[r + 1]);
                    }
                    else if (nums[st] + nums[l] + nums[r] < 0) { 
                        do {  l++; }while (l < r && nums[l - 1] == nums[l]);
                    }
                    else { 
                        do {  r--; }while (l < r && nums[r] == nums[r + 1]);
                    }
                }
            }
            return res;
        }
    };

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/2c552ff7020b4e8fa185c08d5341fd96.png