首页 > 其他分享 >LeetCode腾讯精选50题 -- 三数之和

LeetCode腾讯精选50题 -- 三数之和

时间:2022-09-26 09:57:11浏览次数:57  
标签:set third nums -- 三数 50 len int result

题目:

 

 分析:由题意,很容易看出可以三层循环,但是时间复杂度就为O(n^3)很容易运行超时,想办法进行简化

(1)排序   要求三数相加为0  ,要是排序之后的数据都为正数,则必然不满足条件 直接break

(2)三者关系   相加为0   则a+b+c=0   即c = -(a + b)则有可能不用循环c   而是通过a和b计算出来

(3)题不存着重复数据,则在循环时,可进行判断前后数据是否一样,一样则不用再次进行操作

代码:

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int len = nums.length;   
        if(len < 3){        //长度不够3  直接返回
            return result;
        }
        Arrays.sort(nums);    //排序
        for(int i = 0;i < len;i ++){
            if(nums[i] > 0) {     //当前数大于0  后面的必全大于0  无法相加为0
                break;
            }
            Integer first = nums[i];   //得到第一位置的数
            if(i > 0 && nums[i] == nums[i - 1]){    //两个数相同,则直接继续下一次循环
                continue;
            }     
            Set<Integer> set = new HashSet<>();    //用于储存第二位置的数
            for(int j = i + 1; j < len;j ++){
                Integer third = nums[j];       //第三位置的数
                Integer second = -(first + third);    //计算第二位置的数
                if(set.contains(second)){      //在set中找是否有数与计算出的第二位置的数相等
                    result.add(new ArrayList<>(Arrays.asList(first,second,third)));   //加入
                    while(j < len - 1 && nums[j] == nums[j + 1])    //同样存在相同的数  继续下一次循环    存着j + 1 则 j < len - 1,否则数组越界
                      j++;
                }
                set.add(third);    //不管满足不满足,先放进去
            }
        }
        return result;
    }
}

时间复杂度则为O(n^2)

标签:set,third,nums,--,三数,50,len,int,result
From: https://www.cnblogs.com/tianhuida/p/16729858.html

相关文章

  • 图像特征提取
    1、角点的定义如果一个点在任意方向的微小变动都会导致灰度很大的变化,那么这个点就被称为角点。也就是一阶导数中的局部最大值就是角点。2、Harris角点检测harris角点具......
  • MJExtension 源码解析
    1.NSObject+MJClass为基类添加了一个Class相关的分类,用于获取设置所有关于Class的配置。1.1核心方法-遍历类的继承树/***遍历所有的类*/+(void)mj_enu......
  • VUE2整合markdown
    下载node.js官网检查安装完成之后的版本信息安装vue环境安装淘宝镜像:npminstall-gcnpm--registry=https://registry.npm.taobao.org安装vue-cli脚手架c......
  • 卷积神经网络
    1.神经网络    对于一个分类任务,用机器学习方法可以做,具体步骤是首先要明确特征和标签,把这个特征标签数据放到机器学习算法里训练,然后保存模型,预测分类准确性。......
  • pl/sql自动提示取消[]
    sqlserver2008R2如何取消表名前後的[]SQLPrompt->Options->Insertedcode->Specialcharacters->Encloseidentifierswithinsquarebrackets[]  ......
  • colorstr函数
    YOLO中有个非常有意思的函数,可以给打印的字符串给予颜色。1defcolorstr(*input):2#Colorsastringhttps://en.wikipedia.org/wiki/ANSI_escape_code,i.e.......
  • 搞透 IOC,Spring IOC 看这篇就够了!
    IOC与AOP属于Spring的核心内容,如果想掌握好Spring你肯定需要对IOC有足够的了解@mikechenIOC的定义IOC是InversionofControl的缩写,多数书籍翻译成“控制反转”。IOC......
  • AndroidStudio_项目配置
    build.gradle//Top-levelbuildfilewhereyoucanaddconfigurationoptionscommontoallsub-projects/modules.buildscript{//fromleanrepositories{maven......
  • this关键字三种用法和super与this关键字图解
    this关键字三种用法super关键字用来访问父类内容,而this关键字用来访问本类内容。用法也有三种:1.在本类的成员方法中,访问本类的成员变量。2.在本类的成员方法中,访问本类的......
  • 百度富文本编辑器UEditor(转载)
    原文地址:解决:百度编辑器UEditor,怎么将图片保存到图片服务器,或者上传到ftp服务器的问题(如果你正在用UE,这篇文章值得你看下)|图片(lmlphp.com)在使用百度编辑器ueditor的......