Leetcode元初第一题， 1. two sum

记录从零开始的正经（每天坚持的那种）刷题之旅， 夹杂一些此时此刻的不一定对的想法， 供君一笑。

问题来了：

https://leetcode.com/problems/two-sum/

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.。

在我看来数据结构大任务是存和取， 同时抉择时间和空间的使用。 这里想找到两个相加等于target的数字， 等于是记录一对数字，那么很好的结构就是map/dict。

其他要素：

1. 同一个元素不能用两次
2. 必定有一个确定解
3. 返回Index而不是元素 4 返回不要求顺序

所以这里设计一个一次遍历的答案：

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        from collections import defaultdict
        d = defaultdict((lambda:-9999))


        for i in range(len(nums)):
            if nums[i] in d.keys():
                return [d[nums[i]],i]

            else:
                d[target-nums[i]] = i

defaultdict 瞎加的， 主要可以避免查询空值的差错， 也可以d = {}， 这里明确有解不担心空应该。

组成 一个 d = {target - nums： index} 的key value组合，如果key不存在，就插入，如果查询numsi 到了对应的key， 那就说明相加为target的结果存在， 对应的index也已经存好了，即 dnumsi , 加上这个index i， 就成了。