Day 8 两数之和

```
'''

Day 8 打卡题：两数之和

首先看下题目描述：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

题目参考链接：https://leetcode-cn.com/problems/two-sum

考察知识点：数组，哈希表(字典)

请补充完整如下代码：

class Solution:

      def twoSum(self, nums: List[int], target: int) -> List[int]:

这道题目大家仔细思考下，想办法写出尽可能高效的代码。提示：牺牲空间换取时间

'''

class Solution:

      def twoSum1(self, nums, target): #使用hash

          d = {}

          for index, num in enumerate(nums):

              if num in d:

                  return [d.get( num ),index]

              else:

                  d[target-num] = index

      def twoSum2(self, nums, target): #使用list

          l = []

          for index, num in enumerate(nums):

              if num in l:

                  return [l.index(num), index]

              else:

                  l.append(target - num)

def test_twoSum():

    s = Solution()

    assert s.twoSum1([2,7,11,15],9)==[0,1]

    assert s.twoSum2([2,7,11,15],9)==[0,1]

```

知道想法和可以做出来是两件事，这道题以前做过，自己想到了暴力法， hashmap的做法也看过高手的解法，敲过，但今天又卡住了。

学算法，对我这种没有天赋的人（大多数人是没有天赋，不是天生就会，就能做好的），就是日攻一卒。

算法里可以用空间换时间，学习中就是用平时的时间换精进的程度。

暴力法，一个一个算，肯定是不合算的，因为可能会试多次不同的组合。无论我们是否做算法题，都应该注意，不要重复计算，否则效率一定低。

用什么方法可以不算很多次呢，那就应该算一次，记住，下一次就不用再计算了。

用list, hash都可以用来“记住”很多东西：

我们可以用list来记住我们需要的值，常规的list是一维的，只能记住我们需要的结果，记不住位置，而我们可以使用list的index位置属性来查询这是第几个元素。

而hash可以同时记住我们需要的值和index。从效率上来看，hash比list查询起来会更快（这只是我的感觉，list是要遍历的，大佬知道的话说说看原理）