LeetCode1 两数之和（Go 语言实现）

分享汇总

题目描述

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

样例

输入
[2,7,11,15]
9
输出
[0,1]

哈希表

用一个哈希表记录之前的数字和下标的映射，检查 taget - 当前数字是否出现过，出现过则找到答案

时间复杂度

$O(N)$

Go 代码

func twoSum(nums []int, target int) []int {
    hash := make(map[int]int, len(nums))
    for index, num := range nums {
        if _, ok := hash[target - num]; ok {
            return []int{hash[target - num], index}
        }
        hash[num] = index
    }
    return []int{}
}

Python 代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}
        for i, n in enumerate(nums):
            if target - n in dict:
                return [dict[target - n], i]
            dict[n] = i
        return []