Leetcode_01 Add Two

发表于 | 分类于

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

1
2
3
4
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

详解：

使用字典存放数据项和对应数组位置
遍历时若找到差值就返回字典中对应数据的位置和现在遍历到的数据位置

复杂度分析：

时间复杂度：O(n):有两次遍历查询，数组遍历O(n),哈希表遍历O(1),

空间复杂度：O(n):需要的额外空间取决于在哈希表中存放数据的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashtable = dict()
        for i,num in enumerate(nums):
            v = target-num #计算差值，在hashtable中查找是否存在
            if v in hashtable:
                return [hashtable[v],i]
            else:#不存在就将数据存放到hashtable中
                hashtable[num]=i