0001.两数之和
题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
可以按任意顺序返回答案。
示例 1：
示例 2：
示例 3：
题解
方法一：暴力枚举
思路及算法
最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x
当使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以只需要在 x 后面的元素中寻找 target - x
复杂度分析
-
时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次
-
空间复杂度：\(O(1)\)
代码实现
package main
import (
"fmt"
)
func twoSum(nums []int, target int) []int {
for i := 0; i < len(nums); i++ {
for j := 0; j < len(nums); j++ {
if j == i {
continue
}
if nums[i]+nums[j] == target {
return []int{i, j}
}
}
}
return []int{0, 0}
}
func main() {
fmt.Printf("%v\n", twoSum([]int{2, 7, 11, 15}, 9))
}
方法二：哈希表
思路及算法
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，需要找出它的索引
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 \(O(N)\) 降低到 \(O(1)\)
这样创建一个哈希表，对于每一个 x，首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配
复杂度分析
-
时间复杂度：\(O(N)\)，其中 \(N\) 是数组中的元素数量。对于每一个元素
x，可以 \(O(1)\) 地寻找target - x -
空间复杂度：\(O(N)\)，其中 \(N\) 是数组中的元素数量。主要为哈希表的开销
代码实现
package main
import (
"fmt"
)
func twoSum(nums []int, target int) []int {
hash := make(map[int]int)
for i := 0; i < len(nums); i++ {
if _, ok := hash[target-nums[i]]; ok {
return []int{i, hash[target-nums[i]]}
}
hash[nums[i]] = i
}
return []int{0, 0}
}
func main() {
fmt.Printf("%v\n", twoSum([]int{2, 7, 11, 15}, 9))
}