（算法题）两数之和解题思路

问题：

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

解法1：

第一种办法是暴力解法，通过两个循环遍历nums的所有元素求和判断，代码：

class Solution(object):

    def twoSum(self, nums, target):

        """

        :type nums: List[int]

        :type target: int

        :rtype: List[int]

        """

        for i in range(len(nums)-1):

            for j in range(i+1,len(nums)):

                if nums[i] + nums[j] == target:

                    return i,j

其中时间复杂度为O(n2)，通过一组测试用例的耗时为5927ms，显然在样本n越大的情况下，耗时越久，比较简单粗暴。

解法2：

第二种优化后的方法，通过一层循环+字典的方式判断。

class Solution:

    def twoSum(self, nums, target):

        """

        :type nums: List[int]

        :type target: int

        :rtype: List[int]

        """

        dic = {}

        for key, num in enumerate(nums):

            num1 = target - num

            if num1 in dic:

                return[dic[num1], key]

            dic[num] = key

由于python中字典是由哈希表实现的，if .. in ..语句时间复杂度实际为O(1)，推导出整体时间复杂度为O(n)，其中通过一组测试用例的耗时仅为88ms，结果上性能明显提升不少。