C++ 之LeetCode刷题记录（三十五）

😄😊😆😃😄😊😆😃

开始cpp刷题之旅。

目标：执行用时击败90%以上使用 C++ 的用户。

在这里插入图片描述

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

解题：

第一题两数之和是一道简单题，这一个三数之和变成了中等题。

思路也比较简单，首先是要对输入的nums从小到大排序。

对排序后的nums取三个数并计算和，只要和为0，就将其作为一维vector推入二维中去。

当取的第一个数大于0时，就可以结束遍历了，因为三个数的和肯定会大于0，就不用再去做后续的操作了。

注意题目中有个要求，输出不可包含重复的三元组。

我们可以在做的时候加个判断，对排序后的nums中满足和为0的三元组，对左指针进行判断，判断其与加一的数是否相同；右指针同样的操作，与减一的数做判断是否相同；如果相同，那么说明会有重复，我们只需在判断条件中加入left++或right–即可，这里的判断要用while进行持续判断，不能使用if。

思路比较简单，代码如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] > 0) right--;
                else if (nums[i] + nums[left] + nums[right] < 0) left++;
                else {
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
};