【LeetCode每天一题】Two Sum(两数之和)

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 exactly one solution, and you may not use the same element twice.

Example:                 Given nums = [2, 7, 11, 15], target = 9,               return [0, 1].             Because nums[0] + nums[1] = 2 + 7 = 9

思路：这个题的解决办法有几种方法。

　　第一种方法是：暴力破解，对数组中每一种可能进行计算看是否满足要求。 但是这种方法的时间复杂度较高 。时间复杂度为O(n²)， 空间复杂度为O(1).

　　第二种方法是：使用字典辅助空间，我们先将数组轮询一遍，将数组中的内容存储到字典中， 存储完毕之后，我们将target减去字典中的第一个值得到另外一值看是否存在在字典中，不存在就继续遍历。直到查找到对应结果。时间复杂度为O（n），空间复杂度为O（n）。这种思路还可以将其改进一下我们在遍历存储得过程中边遍历边查找。。如果查找到了就直接返回。否则就继续存储查找。改进之后得时间空间复杂度还是不变。那为什么叫改进呢?因为之前得解决办法，空间复杂度一定为O（n），但是改进之后得最坏得情况空间复杂度为O（n），但这只是个别情况，大部分情况下都不可能存在最坏得情况，都有可能存储了二分之一得空间就找到结果了。所以称其为改进之后得办法。

代码：

 1 class Solution(object):
 2     def twoSum(self, nums, target):
 3         """
 4         :type nums: List[int]
 5         :type target: int
 6         :rtype: List[int]
 7         """
 8         if len(nums) < 0:
 9             return []
10         tem_dict = {}                        # 申请辅助空间
11         for i in range(len(nums)):           # 遍历数组
12             if (target - nums[i]) not in tem_dict:      # 查找另外一个数是否在字典中
13                 tem_dict[nums[i]] = i                     # 不存在就其和下标进行存储。
14             else:
15                 return [tem_dict[target-nums[i]], i]      # 存在的话就返回其下标
16         return [-1, -1]       # 数组中不存在。

【LeetCode每天一题】Two Sum(两数之和)

原文：https://www.cnblogs.com/GoodRnne/p/10603029.html