leetcode解题记录-1.两数之和

给定一个整数数组 nums 和一个目标值

target

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/two-sum

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

采用以空间换时间的方式，通过一次遍历，找到答案。

首先构建一个哈希表。

在遍历每个元素的时候，做两件事：

1. key为当前元素的值，value为当前下标，添加到哈希表中，所以当遍历到第n个元素的时候，哈希表中应该已经存在n-1个元素。
2. 当遍历到第n个元素的时候，去哈希表中查找

   target - nums[n]

   的值。如果查找成功，则当前值的下标，与哈希表中查找到的value即为我们要找的答案。如果找不到，则继续遍历。

最坏的情况是遍历完整个数据，才找到答案。由于哈希表的查找时间复杂度为

O(1)

，所以整个算法的时间复杂度为

O(n)

。

code

• python3

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        pass_index_map = dict()
        for index, value in enumerate(nums):
            if pass_index_map.get(target-value) is not None:
                return [pass_index_map.get(target-value), index]
            pass_index_map[value] = index
        return [None, None]
           

• Go

func twoSum(nums []int, target int) []int {
    passedIndexMap := make(map[int]int)
	for index := 0; index < len(nums); index++ {
		r := target - nums[index]
		lastIndex, ok := passedIndexMap[r]
		if ok {
			return []int{lastIndex, index}
		}
		passedIndexMap[nums[index]] = index
	}
	return []int{1, 2} 
}