1. Two sum， python解法

题目

题目要点

I/O 数据结构

• Given: nums -> array, target -> int
• Return type: list

其他

• array中同一元素只能用一次

解题思路

初级解法

1. 首先最初级的是θ(n^2)解法，数组中每一元素(i)都与其他元素(j)相加,伪代码如下

   n=len(nums)
   for i from 0 to n-1:
   for j from (i+1) to n:
    if nums[i]+nums[j] == target:
      return [i,j]

进阶解法

1. 进阶解法，利用hashmap中查找是O(1)的特性，把array存入hashmap中，只循环一遍就可以找到解。

这里我也是查资料才知道的，python中的dictionary利用了hashmap的存储特性，而dictionary作为python中应该都接触过的重要数据结构之一,我们可以认为在python中dictionary相当于hashmap的一种表现形式。

那么我们的重点就在于，如何创建和使用这个dictionary。
进阶一，代码如下

hashmap = {}
for i in range(len(nums)):
    hashmap[nums[i]] = i
for i in range(len(nums)):
    complement = target - nums[i]
    if complement in hashmap and hashmap[complement] != i:
        return [i, hashmap[complement]]

先存再比较，注意要避免查找到的index是循环中的i（自己加自己等于target）

进阶二，代码如下

hashmap = {}
for i in range (0,len(nums)):
    complement = target - nums[i]
    if complement in hashmap:
        return [i,hashmap[complement]]
    hashmap[nums[i]]=i

边存边比较。原理同上

一个小问题

以上进阶方法有一个小bug，我们的hashmap是不完整的。
举例说明 nums=[1,2,2,5], target=6
如果我们尝试print整个hashmap则会发现
{1: 0, 2: 2, 5: 3}
可以看到，第二个元素没有被存入hashmap中！！
原因是hashmap[nums[i]]=i在执行第三个元素的时候，因为它的key也是2，导致原来的2:1被改写成了2:2
虽然对这道题的答案不影响，但是如果我们想什么时候调用hashmap，很明显
hashmap = {number:index} 的这种写法会带来很多困扰

那么如果我们用hashmap = {index:number}的这种写法呢？例如 {0:1,1:2,2:2,3:5}

hashmap={}
for i in range(len(nums)):
    hashmap[i] = nums[i]
for i in range(len(nums)):
    complement = target - nums[i]
    if complement in hashmap.values():
        complement_index = list(hashmap.values()).index(complement)
        if(complement_index != i):
            return ([i, complement_index])

这里我们在find index时用了一个小小的转换在line7（find the key by given a value in a dict), 因为dict只能通过dict[key]得到或查找value,没有办法通过value反向得到key。所以我们需要用dict.values()得到所有的value，并将它转换成list，通过list中的index() method来得到index。

hashmap = {}
for i in range (0,len(nums)):
    complement = target - nums[i]
    if complement in hashmap.values():
        complement_index = list(hashmap.values()).index(complement)
        return [i,complement_index]
    hashmap[i]=nums[i]

转换方法同上。

dict methods

总结

可以明显看出进阶方法是更快速的，并且在题目范围内，我们不用在意hashmap的完整性。因为我们之后的改良代码其实要比进阶方法用更慢一点，且memory也用的更多一点，原因就是我们需要多用一个list的转换来得到index。

但是通过以上的练习，我们学到了。

• 创建和使用python中的dictionary （hashmap）
• 使用dict中的values(), keys()等函数
• 通过value找到key