LeetCode 1. Two Sum Python Solution

此题目对应于 LeetCode 1

题目要求：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have same element twice.

给一个数组和一个数值，数组中有两个元素的和等于给定数值，求该两个元素在原数组中对应下标

这里我提供2个解法

解法1：粗暴解法，时间O(n^2),LeetCode运行时间 4945 ms

class Solution(object):
    def twoSum(self, nums, target):
        if len(nums)<2:
            return None
        if len(nums)==2:
            return [0,1]
        for i in range(len(nums)):
            left = nums[i]
            for j in range(i+1,len(nums)):
                right = nums[j]
                if left+right == target:
                    return [i,j]

解法2：采取辅助的dict数据结构，只需进行一次遍历，时间O(n)，LeetCode运行时间 35ms

值得注意的是判断某个key是否存在于dict中的时间复杂度是O(1)的，dict采用了hash的算法。

class Solution(object):
    def twoSum(self, nums, target):
        if len(nums)<2:
            return None
        if len(nums)==2:
            return [0,1]
        dic = {}
        for i in range(len(nums)):
            if nums[i] in dic:
                return [dic[nums[i]],i]
            else:
                dic[target-nums[i]] = i

参考文章

https://discuss.leetcode.com/topic/23004/here-is-a-python-solution-in-o-n-time