导语：LeetCode一道简单题 Two Sum

题目

给定一个整形数组，请返回和为某个值的两个数的角标。

你可以假设数组中只有一组符合条件的元素，而且同一个元素不允许使用两次。

第一种简单解法：暴力法

两层循环，时间复杂度为O(n^2) 空间复杂度为O(1)

第二种解法：HashMap两次迭代

为了降低时间复杂度，显然要对代码进行修改。

我们思考用哪种数据结构适合记录 索引和数值之间的对应关系呢？

显然可以使用HashMap

这样通过用空间换时间，将查找元素的时间复杂度由O(n^2) 降到了O(1)。

下面的例子使用两次map迭代，第一次存储数组信息，第二次循环时判断条件是否满足。

HashMap每次一次查询元素的时间是O(1) ，所以整个程序的时间复杂度为O(n) 。

map中存放n个数字，空间复杂度为O(n)

第二种解法：HashMap一次遍历

在迭代过程中，查看map中是否已经存在需要的数字，如果存在将结果返回，如果不存在将当前遍历的元素插入map中。

时间复杂度和空间复杂度都是O(n)，但是只需要一次迭代。

本文内容由小娴整理编辑！