le中查找元素时间为常数的优势，如果找到了就结束，此处需要注意的是，如果数组中有重复的值出现，那么第二次出现时就不会加入到hashtable里了，比如3,4,3,6；target=6时，当循环到第二个3时，也可以得到正确结果。
代码如下：
class Solution {
public:
vector
twoSum(vector
&numbers, int target) { int i, sum; vector
results; map
hmap; for(i=0; i
(numbers[i], i)); } // find the number which equal to target - numbers[i] if(hmap.count(target-numbers[i])) { int n=hmap[target-numbers[i]]; if(n
Python:
class Solution:
# @return a tuple, (index1, index2)
def twoSum(self, num, target):
length = len(num)
index = []
hash_tab = {}
for i in range(length):
if( not hash_tab.has_key(num[i])) :
pair = {num[i] : i}
hash_tab.update(pair)
if( hash_tab.has_key(target - num[i] )) :
n = hash_tab[target-num[i]]
if n< i :
index.append(n + 1)
index.append(i + 1)
result = tuple(index)
return result
return result
Summary
首先想到的就是两层遍历法，但是显然时间复杂度太高，是O(N^2)，不符合要求. 于是就应该想如何降低复杂度，首先应该想将逐个比较转变为直接查找，即首先计算出 target与当前元素的差，然后在序列中寻找这个差值，这样首先就把问题简化了，而寻找的过程可以先对序列进行快排，然后二分查找，这样整体的复杂度就降低为 O(N*logN) 了；查找最快的方法是利用一个 map容器存储每个元素的索引，这样取得某个特定元素的索引只需要常数时间即可完成，这样就更快了，最多只需遍历一次序列，将元素及其索引加入map中，在遍历的过程中进行对应差值的查找，如果找到了就结束遍历，这样时间复杂度最多为 O(N)，It's amazing！
总之，这是自己做的第一道leetcode题，感觉比其他oj要严格一些，比如这题有严格的执行时间要求，O(N^2)的不能过，可以给自己优化程序的理由。继续加油！
提交记录:
