本文共 4241 字，大约阅读时间需要 14 分钟。

目录

题目描述

给定一个整数数组nums和一个目标值target，请你在该数据中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

输入/输出示例：

解决方案

方案一：二重循环检索

在二重循环里查找是否存在两个值的和与target相等。

for _, i := range nums:    for _, j := range nums:        if i + j == target {            // find!        }

如果找到满足条件的值，就讲对应元素的下标收集起来。最终将所有满足条件的下标所组成的列表返回。

但是这个方案有一个致命的缺点：时间复杂度为，也就是说大量的时间被浪费在重复的计算上，因此不是最优解。

方案二：使用Map和集合查找

集合Set是一个不重复的序列。在Go中由于不存在Set类型，我们可以使用Map来构造Set。

减少无意义的循环嵌套是提高运行效率的方法。将数组切片存放在Map中，以数值为key，以索引为值，就可以使用两个叠加循环得解：

for index, value := range nums {    numsMap[value] = index}for value := range nums {    _, ok := numsMap[target - value]    if ok {        // find    }}

考虑到数组切片中可能出现多个相同的数值，因此字典的value应该是一个集合。即集合保存了数组中某个值的所有索引。

代码

package mainimport "fmt"type Set struct {	Base	map[int]string}func CreateSet() *Set {	set := new(Set)	set.Base = make(map[int]string)	return set}func (s *Set) Add(data int) {	s.Base[data] = ""	return}func (s *Set) Adds(data... int) {	for _, d := range data {		s.Base[d] = ""	}}func (s *Set) Exist(data int) bool {	_, ok := s.Base[data]	return ok}func (s *Set) Pop() (int, error) {	if s.Length() <= 0 {		return 0, fmt.Errorf("can not pop element: set is empty")	}	for key := range s.Base {		value := key		delete(s.Base, value)		return value, nil	}	return 0, nil}func (s *Set) Length() int {	return len(s.Base)}func (s *Set) ToSlice() []int {	result := make([]int, 0)	for data := range s.Base {		result = append(result, data)	}	return result}func twoSum(nums []int, target int) []int {	numsMap := make(map[int]*Set)	for index, num := range nums {		_, ok := numsMap[num]		if !ok {			numsMap[num] = CreateSet()		}		numsMap[num].Add(index)	}	result := CreateSet()	for value := range numsMap {		_, ok := numsMap[target - value]		if !ok {			continue		}		index1, err := numsMap[value].Pop()		if err != nil {			continue		}		if numsMap[value].Length() <= 0 {			delete(numsMap, value)		}		_, ok = numsMap[target - value]		if !ok {			continue		}		index2, err := numsMap[target - value].Pop()		if err != nil {			continue		}		if numsMap[target - value].Length() <= 0 {			delete(numsMap, target-value)		}		result.Adds(index1, index2)	}	return result.ToSlice()}

代码走读

package mainimport "fmt"// ---------- 定义集合结构 ----------// 本质上集合使用map来存储数据type Set struct {	Base	map[int]string}// 创建一个集合func CreateSet() *Set {	set := new(Set)	set.Base = make(map[int]string)	return set}// 向集合中添加一个元素func (s *Set) Add(data int) {	s.Base[data] = ""	return}// 向集合中添加多个元素func (s *Set) Adds(data... int) {	for _, d := range data {		s.Base[d] = ""	}}// 判断元素是否在集合中存在func (s *Set) Exist(data int) bool {	_, ok := s.Base[data]	return ok}// 将集合中的一个随机元素弹出，并返回该元素func (s *Set) Pop() (int, error) {	if s.Length() <= 0 {		return 0, fmt.Errorf("can not pop element: set is empty")	}	for key := range s.Base {		value := key		delete(s.Base, value)		return value, nil	}	return 0, nil}// 求集合长度func (s *Set) Length() int {	return len(s.Base)}// 将集合转换为切片func (s *Set) ToSlice() []int {	result := make([]int, 0)	for data := range s.Base {		result = append(result, data)	}	return result}// LeetCode定义解决函数func twoSum(nums []int, target int) []int {    // 将数组切片转换为Map，Map的key保存数组切片的值，value是一个Set, 保存了值对应在切片中的所有     // 索引下标	numsMap := make(map[int]*Set)	for index, num := range nums {		_, ok := numsMap[num]		if !ok {			numsMap[num] = CreateSet()		}		numsMap[num].Add(index)	}    // 将所有找到的结果放入result中	result := CreateSet()	for value := range numsMap {		_, ok := numsMap[target - value]		if !ok {            // 如果没有找到，则进行下次遍历			continue		}        // 找出第一个元素的下标，如果集合为空，则将该值从Map中删除		index1, err := numsMap[value].Pop()		if err != nil {			continue		}		if numsMap[value].Length() <= 0 {			delete(numsMap, value)		}        // 需要再次判断的原因是数组切片中存在某个数恰巧是target值的一半，且该数值只存在一个，没有        // 配对的另一个值。因此index1会获取到下标，但是会将该value的键值对删除		_, ok = numsMap[target - value]		if !ok {			continue		}		index2, err := numsMap[target - value].Pop()		if err != nil {			continue		}		if numsMap[target - value].Length() <= 0 {			delete(numsMap, target-value)		}        // 将结果放入result中		result.Adds(index1, index2)	}    // 转换成数组切片输出	return result.ToSlice()}// 自测用例func main() {	r := twoSum([]int{2, 7, 11, 15}, 9)	fmt.Println(r)}

传送门

转载地址：http://sdsoi.baihongyu.com/