本文共 3507 字，大约阅读时间需要 11 分钟。

1. 题目描述
2. 题解和思路
3. 代码
4. 优质代码
5. 闲话

题目描述

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

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

实例

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

[

[-1, 0, 1],

[-1, -1, 2]

]

思路

大家好!!愧疚啊,这几天都没有写题解了!!!呜呜呜!

聪明的小伙伴是不是一看题目之后,仔细的想了想第一思路就是三重循环,直接出来答案!其实是对的,但是转念一想时间复杂度O(n^3),这是一个很长的时间,而且你有么有想过,如果你直接三重循环,可能会输出重复的三元数组.所以简单直接的三重循环是不可取得,需要进行优化.

1. 第一步优化,我们先让输出不会输出重复的三元数组,这个数组是无序,我们可以先进行排序,排序之后是有序的,然后输出的三元数组(a,b,c)保证a<b<c这样是不是不会有重复的了呢.
2. 第二步优化,我们就要减小时间复杂度,让时间复杂度从三次降到二次,那么你想想是不是要少一重循环,至于少哪一重,你可以先这样考虑,在a不变的情况下,b必须小于c,如果b变大了,那么c就要减小,既然要这样,让b从头开始遍历,而c则从尾部开始遍历.而且我们要少一重循环,那么可以用双指针的方法去完成我们的要求.
3. 已经减了枝,也满足了要求,第三步就不是优化了,你得写代码了!

其实写题目我们一般脑袋第一思考都是暴力去解决的,(天才就不考虑了),很多时候你可以用很多方法去给你的暴力方法去优化,用二分方法,排序等等很多方法优化的,一直优化,知道时间复杂度满足要求的.

代码

class Solution {
   public:    vector
   
    
     > threeSum(vector
     
      & nums) {
           int n = nums.size();        sort(nums.begin(), nums.end());        vector
      
       
        > ans;        // 枚举 a        for (int first = 0; first < n; ++first) {
               // 需要和上一次枚举的数不相同            if (first > 0 && nums[first] == nums[first - 1]) {
                   continue;            }            // c 对应的指针初始指向数组的最右端            int third = n - 1;            int target = -nums[first];            // 枚举 b            for (int second = first + 1; second < n; ++second) {
                   // 需要和上一次枚举的数不相同                if (second > first + 1 && nums[second] == nums[second - 1]) {
                       continue;                }                // 需要保证 b 的指针在 c 的指针的左侧                while (second < third && nums[second] + nums[third] > target) {
                       --third;                }                // 如果指针重合，随着 b 后续的增加                // 就不会有满足 a+b+c=0 并且 b
       
      
     
    
   

我的代码和官方其实差不多的,我没有写注释,所以你们看看这个官方的吧!

写完了leetcode题目我们也去看看别人的优质代码,提高自己,所以看看时间复杂度更低的代码吧!!

class Solution {
   public:    vector
   
    
     > threeSum(vector
     
      & nums) {
           vector
      
       
        > res;        sort(nums.begin(), nums.end());        int len = nums.size();        if (len < 3 || nums[0] > 0 || nums.back() < 0) {
               return res;        }        for (int idx = 0; idx < len - 2; ++idx) {
               int fix = nums[idx];            if (fix > 0) {
                   break;            }            if (idx > 0 && fix == nums[idx - 1]) {
                   continue;            }            int left = idx + 1;            int right = len - 1;            while (left < right) {
                   auto total = nums[left] + nums[right];                if (total == -fix) {
                       if (left == idx + 1 || right == len - 1) {
                           res.push_back({
   nums[idx], nums[left], nums[right]});                        ++left;                        --right;                    } else if (nums[left] == nums[left - 1]) {
                           ++left;                    } else if (nums[right] == nums[right + 1]) {
                           --right;                    } else {
                           res.push_back({
   nums[idx], nums[left], nums[right]});                        ++left;                        --right;                    }                } else if (total > -fix) {
                       --right;                } else {
                       ++left;                }            }        }        return res;    }};
       
      
     
    
   

这个代码很强,时间只需要40ms我们得多学习学习,没有注释,所以你们好好思考一下!!!

闲话

最近考试挺多的,慢慢的也接近了尾声了.这几天我得好好复习高数,这是一个难题!!!

大家好,我是大一小菜鸡,又菜瘾还大.

转载地址：http://dxdki.baihongyu.com/