题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。

解法

• 双指针

暴力法时间复杂度O(n^2)

#
# @lc app=leetcode.cn id=1 lang=python3
#
# [1] 两数之和
#

# @lc code=start
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i]+nums[j] == target:
                    return [i,j]
# @lc code=end

• Hashmap
  散列表也称作哈希表，这种数据结构提供了key 和 value的映射关系。只要提供一个key，就可以高效查找到它所匹配的value, 时间复杂度接近于O(1)。

在python中也提供了dict(字典)

思路：查找第一个元素对应的sub = target - nums[0] 是否在map里面，无则将第一个元素添加到map; 再查找第二个元素对应sub = target - nums[1] 是否在map，有则return，无则将第二个元素添加到map;以此类推。
此时用哈希表替代了暴力求解法的第二个遍历（找sub），哈希表时间复杂度O(1)

总时间复杂度O(n)

# @lc app=leetcode.cn id=1 lang=python3
#
# [1] 两数之和
#

# @lc code=start
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = {}
        for i in range(len(nums)):
            sub = target - nums[i]
            if sub in map.keys():
                return [map[sub],i]
            
            else:
                map[nums[i]] = i

# @lc code=end