力扣 1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
方案一：利用无需映射 map，保留遍历途中经过的每隔数，每经过一个数判断一次 map[target - num] 是否存在。
func twoSum(nums []int, target int) []int {
mp := make(map[int]int, len(nums))
for idx, num := range nums {
if v, ok := mp[target - num]; ok {
return []int{v, idx}
}
mp[num] = idx
}
return nil
}
- 时间复杂度：O(n)，因为需要遍历数组中所有所有数字，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，因为使用了长度不超过 n 的无序映射，所以空间复杂度为 O(n)。
方案二：双指针，先记录元素下标和值，然后进行快排，计算指针指向元素的和。
type node struct {
idx, val int // 数组下标和值
}
func twoSum(nums []int, target int) []int {
// 构建 node 数组
nodes := make([]*node, len(nums))
// 遍历 nums，记录元素下标和值
for i, v := range nums {
nodes[i] = &node{
idx: i,
val: v,
}
}
// 自定义排序，使得节点元素按照 val 递增（时间复杂度约 nlogn）
sort.Slice(nodes, func(i, j int) bool { return nodes[i].val < nodes[j].val })
// 定义双指针，分别指向 nodes 数组头和尾
l, r := 0, len(nodes) - 1
for l < r {
// 计算两个指针指向的节点的 val 的和
switch sum := nodes[l].val + nodes[r].val; {
case sum > target:
r--
case sum < target:
l++
default:
return []int{nodes[l].idx, nodes[r].idx}
}
}
return nil
}
- 时间复杂度：O(nlogn)，程序中存在多次长度不大于 n 的遍历以及一次自定义排序（越耗时 nlogn），所以时间复杂度为 O(nlogn)。
- 空间复杂度：O(nlogn)，因为使用了长度为 n 的数组 nodes，但快排造成的空间消耗为 nlogn，所以空间复杂度为 O(nlogn)。