技术文章第一时间送达!
最近ofo的消息很是火爆,前段时间,很多人去ofo的总部要求退押金,场面很是震撼,因此有网友戏称为北京车友会。个人觉得,说实话,为了这部分押金真的跑去北京讨还押金,确实有点不值得,因为和你的时间成本相比,根本就不值。如果是咽不下这个口气,完全没必要,就当喂狗了。
同时这也成为了压倒ofo的最后一根稻草,本来还能活一段时间的ofo,这下可能加快倒闭的速度了,就是不知道会不会像乐视某掌门人一样....
最近,也打算组织一个交流群,文章末尾有我的个人微信,有兴趣的小伙伴可以添加一下,有些问题,我们也可以交流一下,添加时记得备注公众号哦。
>>>> 步入正题
给定一个整数数组 nums
和一个目标值 target
,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
题目解析:
通过示例可以看出,数组下标0+数组下标1的值,要等于target参数。如果要找出数组中满足条件的数据,那么就要用到循环了,通过遍历这个循环,用数组中前一个下标和后一个下标进行对比,如果两个下标的值相加等于target变量,那么就返回它们,如果没有的话,没关系,我们throw一个异常。
解题代码:
方法一:暴力法
遍历每个元素x,并查找是否存在一个值与它的和等于target
测试结果:
方法二:一遍哈希表
迭代的时候将元素插入到表中的同时,检查哈斯表中是否已经存在当前元素对应的目标元素,也就是target - x,如果它存在,那我们已经找到了对应解,并立即将其返回。
代码解析:
//如果此映射包含指定键的映射,则返回true
boolean containsKey(Object key)
测试结果:
总结:
1、第一种方法,对于每个元素,我们试图通过遍历数组的其余部分来寻找它所对应的目标元素,时间虽然比第二种慢,但是空间占用比第二种方法少。
2、相比较第一种方法,第二种方法,我们只遍历了包含有n个元素的列表一次,在时间上是比第一种快的,但是使用了一个Map,在空间占用上比第一种方法大,用空间换取时间。时间复杂度:O(n) 空间复杂度:O(n)。
时间复杂度与空间复杂度参考这篇文章:时空复杂度O(n^2)、O(n)、O(1)、O(logn)、O(nlogn)是什么意思