首页 > 搜索 > 两数字和算法,每天一点算法-

两数字和算法,每天一点算法-

互联网 2020-10-20 16:06:14
在线算命,八字测算命理
题目描述

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例

给定 num=[2,7,11,15], target = 9

返回:[0,1]

难度

简单

解题思路

这道题的思路是遍历数组,每次以第一个数为一个加数a,求出另一个加数b应该是多少,然后再遍历数组是否有b,如果有则返回,没有就继续循环

方法1:暴力求解

使用双重循环,外层循环用来遍历加数a,内层循环用来检索加数b是否在数组中

方法1

 

复杂度分析

时间复杂度:O(n^2)

空间复杂度:O(n)

方法2:利用HashMap

方法1使用遍历的方法来确定加数b是否在数组中,需要的时间为O(n),考虑到HashMap的特性,这里可以使用一个HashMap来存放数组的值和下标,可以实现在O(1)的时间内判断加数b是否在数组中

方法2

复杂度分析

时间复杂度:O(n)

空间复杂度:O(n)

方法对比

使用leetcode测试的数据可以很明显看出两种方式的差异

测试结果

很明显,使用了HashMap之后程序的直行时间大大减少

本篇完

2020-4-22 晚

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多