两数之和

题目描述

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

解题思路

自做

通过第一层循环获得第一个数，遍历后方的数获得第二个数，判断两数之和是否等于目标值。

// 23ms
func twoSum(nums []int, target int) []int {
    length := len(nums)
    for k, v := range nums {
        i := k + 1
        for {
            if i == length {
                break
            }
            if v+nums[i] == target {
                return []int{k, i}
            }
            i++
        }
    }
    return nil
}

学习

注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)降低到 O(1)。

这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

// 4ms
func twoSum(nums []int, target int) []int {
    hashTable := map[int]int{}
    for i, x := range nums {
        if p, ok := hashTable[target-x]; ok {
            return []int{p, i}
        }
        hashTable[x] = i
    }
    return nil
}

总结

今天刷了一道简单的题目，两数之和。自己的解法是暴力解法，时间复杂度较高。学习了哈希表的解法，时间复杂度降低到 O(1)。

注意到哈希表的解法通过空间换时间的方式，将时间复杂度降低到 O(1)。学习了哈希表的使用，未来需要多考虑哈希表的使用。

明天继续刷题，加油！