2023-07-08 LeetCode每日一题（三数之和）-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023-07-08 LeetCode每日一题（三数之和）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023-07-08每日一题

一、题目编号

15. 三数之和

二、题目链接

点击跳转到题目位置

三、题目描述

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

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

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

3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵

四、解题代码

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

五、解题思路

(1) 这个题目是要从数组中找出相加等于0的三个数的所有组合，那么问题就转化成<1> 如何找数字<2> 如何不重不漏。

(2) 如果使用最朴素的三重循环的方法暴力枚举的话，时间复杂度一定超过系统判定的范围，一定是错的，那就得寻找其他的方法，遇到这类问题，我们一般采用的排序的方式先进性预处理。将数组按照数字从小到大进行排序。而且我们已知道数组一定至少有三个元素，那么我们先判断最小的三个数字加起来是否大于0，如果最小的三个数字相加都大于0的话，那么一定不存在符合要求的三元组。

(3) 遍历数组，通过指针i进行，用来找第一个数字，如果i 不等于0并且nums[i] 等于nums[i-1]则跳过判断（因为第一个数字重复了）。

(4) 第一个数字确定下来了，剩下的两个数字是在区间[i + 1, n - 1]中获取。采用双指针，left指向i+1，right指向n-1。记temp 等于nums[i] + nums[left] + nums[right]，如果temp等于0，则表示是一个结果，left++，right–，然后判断nums[left] 是否等于 nums[left - 1]和nums[right] 是否等于nums[right + 1]，等于的话指针要继续移动，并且只要left < right，指针就可以移动。如果temp小于0，则说明数小了，左指针右移。如果temp大于0，则说明数大了，右指针左移。

(5) 最终返回结果数组即可。文章来源地址https://www.toymoban.com/news/detail-542068.html

到了这里，关于2023-07-08 LeetCode每日一题（三数之和）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！