[每日一题]1. two-sum(字典)

1.这是一道判断字典的题目，就是在list中找到两个数能够相加得到target value。

链接：https://leetcode.com/problems/two-sum/

1-two-sum.JPG

这题的做法有两种，
第一种：暴力求法，两层循环，找到相加为target value的值
O(n) = n^2
第二种：
1.建立个{index: value}的字典。
2.做一次循环，从字典中找到num = target - nums[i]的值。
O(n) = n

2.题解：

方法一：

class Solution:
    def twoSum(self, nums, target):
        L = []
        for i in range(0, len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j] == target:
                    L.append(i)
                    L.append(j)
                    return L

方法二：

# coding = utf-8
class Solution:
    def twoSum(self, nums, target):
        # 建立字典{编号：数值}
        # 通过zip建立，将两个list打包成元组
        dict_num = dict(zip(nums, range(len(nums))))
        # print(dict_num)

        L = []
        # 遍历一遍
        for i in range(0, len(dict_num)):
            find_num = target - nums[i]
            # 在字典中查找是否有这个符号，并比对编号是否一致，来判断是否满足要求。
            if find_num in dict_num \
                    and dict_num[find_num] is not i:
                j = dict_num[find_num]
                L.append(i)
                L.append(j)
                return L

3.完整代码

查看链接：
https://github.com/Wind0ranger/LeetcodeLearn/blob/master/4-dict/1-two-sum.py