专栏首页java工会leetcode两数求和从初步到优化

leetcode两数求和从初步到优化

前言

◆ ◆ ◆ ◆

上周有小伙伴去面试,小明问了一下面试的情况,顺便问问题目。他说有一道题是根据输入数组以及结果,返回两数的数组下标。这个听着就很熟悉,因为leetcode的第一题,于是就重新回顾了一下。

题目

◆ ◆ ◆ ◆

顺便找了个中文版:

方法一

◆ ◆ ◆ ◆

初步第一眼看着并不难,因为是两个for循环遍历一下,就可以找出结果,方法比较粗暴

时间复杂度:两层 for 循环,O(n²)

空间复杂度:O(1)

方法二

◆ ◆ ◆ ◆

上面的方法比较粗暴,优化空间还是有的。最大的问题就是两重for循环,首先解决的是能不能一个for循环就能搞定。

我们看一下核心代码:

换一个理解:

for(int j=(i+1);j<nums.length;j++){ sub=target-nums[i] if(nums[j]==sub){ }

第二层 for 循环的作用是是遍历所有的元素,看哪个元素等于sub,时间复杂度为 O(n)。

有没有一种方法,不用遍历就可以找到元素里有没有等于 sub 的?

我们最爱的hashMap!

我们可以把数组的每个元素的值保存为map 的 key,下标保存为 value 。

这样只需判断sub是否存在于map就行,而此时的时间复杂度仅为 O(1)。

于是就有了第二种方法:

时间复杂度:O(n)

空间复杂度:所谓的空间换时间,hashMap 的空间复杂度变为 O(n)

方法三

◆ ◆ ◆ ◆

方法二中的的第一个for仅仅起到赋值作用,而这个赋值好像是可以加到下面的for当中的。于是就有了方法三:

当然这个也有个小问题,因为如果第一个数是结果中的某一个的话,第一次的map中是找不到它的,所以这个有个小问题,欢迎大神加微信交流~miraclesComing

总结

◆ ◆ ◆ ◆

程序优化里面,空间换时间,时间换空间,都是一个比较常用的方法,牺牲小部分来换取高性能,其实还是可取的。

本文分享自微信公众号 - java工会(javagonghui),作者:小明同学

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Spring Boot 入门

    Spring Boot 是由 Pivotal 团队提供的基于 Spring 的全新框架,其设计目的是为了简化 Spring 应用的搭建和开发过程。该框架遵循“约...

    三哥
  • Linux Shell从入门到删除根目录跑路指南

    shell 作为一门 linux 下使用广泛的系统语言,语法简单,上手容易,但是想要用好,少犯错误,也不是那么容易的一件事,可谓虽是居家旅行之良药,但也是杀人灭...

    三哥
  • Linux Shell从入门到删除根目录跑路指南

    三哥
  • 经典!工业界深度推荐系统与CTR预估必读的论文汇总

    导读:本文是“深度推荐系统”专栏的第十一篇文章,这个系列将介绍在深度学习的强力驱动下,给推荐系统工业界所带来的最前沿的变化。本文主要根据Google推出的引领推...

    AI科技大本营
  • HLS中循环的并行性(1)

    Vitis HLS尽可能地探测代码中的并行性,以降低Latency。但对于for循环,即使两个for循环是相互独立、毫无关联的,在默认情形下,工具也不会对其进行...

    Lauren的FPGA
  • JS中的for循环——你可能不知道的点。

    for循环中出现多个异步函数(比如ajax请求,或者node后端执行一些数据库操作或文件操作),如果想要这些异步串行变为同步应该怎么做?

    coder_koala
  • JS中的for循环——你可能不知道的点。

    for循环中出现多个异步函数(比如ajax请求,或者node后端执行一些数据库操作或文件操作),如果想要这些异步串行变为同步应该怎么做?

    用户1462769
  • 《机器学习实战(Scala实现)》(三)——决策树

    用户1621453
  • RTB业务知识之2-Impression概念和关键属性

      This object describes an ad placement or impression being auctioned. A single ...

    数据饕餮
  • Linux运维基础技能: 脚本编程与Linux命令

    本系列文章一共三篇,分别为《脚本编程与 Linux 命令》、《接入层与网络基础》和《 MySQL 与 SQL 优化》,由腾讯高级工程师 luaruan(阮永顺)...

    张戈

扫码关注云+社区

领取腾讯云代金券