请实现一个函数，输入一个整数数组和一个目标值，在数组中找到两个数使得它们的和等于目标值。

今日份AI出笔试题：

AI Golang笔试中级题目https://bs.rongapi.cn/1702565828114780160/23

完整题目：

请实现一个函数，输入一个整数数组和一个目标值，在数组中找到两个数使得它们的和等于目标值。函数应该返回这两个数的索引，其中索引1必须小于索引2。可以假设每个输入只对应一种答案，而且同样的元素不会被重复利用。例如，给定数组 [2, 7, 11, 15] 和目标值 9，因为 nums[0] + nums[1] = 2 + 7 = 9，返回 [0, 1]。

思路：

这个题目拿到手之后，第一直觉是直接双循环，循环拿到第一个数，在剩余的里面去查找第二个数，查到了就提交。

那作为中级题目，我们还是要稍微做一下优化的。

我的优化思路是既然做了循环，有没有可能在过程中做一些缓存数据，加速之后的查找？

开始想要不要直接做个排序，后来觉得排序本身也要计算量，而且这道题不需要完整排序，应该是要比排序快的。

顺着这个思路，我想每次既然比较了一个数值，那我可以在这个过程中把原始数据按大小分成两个部分？

这样外层循环一次，我就能得到粒度更细的一个分组，下次比较，太小的和太大的值都可以直接忽略，再把命中的数组分成两个就好了，比如上面这个例子，如果第二次查找2，那我只需要比较5以下的第一个分组，第二个分组直接跳过

提交结果在最开始的链接里，但是提交之后，AI觉得问题如下：

答案评价：代码逻辑基本正确，但是存在一些冗余的部分。对于分组的处理可以简化一些，并且可以使用map来存储已经遍历过的元素以提高查找效率。

才想起来，直接用map就可以了……就是边循环，便把位置和值信息存到一个map里，之后如果map里有对应值，就拿出来直接返回，如果没有就再循环。

不过我的方案对于需要返回多个可能值的情况还是有帮助的，把修正后的方案贴出来大家指正：

 
type Group struct {
	Seperator *int
	Values    [][2]int
}
 
func seperateGroup(seperator int, group *Group) (loc int, smallerGroup *Group, biggerGroup *Group, matched bool) {
	smallerGroup, biggerGroup = &Group{
		Seperator: &seperator,
	}, &Group{
		Seperator: group.Seperator,
	}
	for j := 0; j < len(group.Values); j++ {
		if group.Values[j][0] == seperator {
			return j, nil, nil, true
		} else if group.Values[j][0] < seperator {
			smallerGroup.Values = append(smallerGroup.Values, group.Values[j])
		} else {
			biggerGroup.Values = append(biggerGroup.Values, group.Values[j])
		}
	}
	return 0, smallerGroup, biggerGroup, false
}
 
func recurse(loc int, arr []int, target int, groups ...*Group) []int {
	if loc == len(arr)-1 {
		return nil
	}
	var cur = arr[loc]
	var remain = target - cur
	var newGroups []*Group
	i := 0
	for ; i < len(groups); i++ {
		if groups[i].Seperator == nil || remain <= *groups[i].Seperator {
			remainLoc, smallerGroup, biggerGroup, matched := seperateGroup(remain, groups[i])
			if matched {
				return []int{loc, groups[i].Values[remainLoc][1]}
			}
			if i == 0 {
				newGroups = []*Group{smallerGroup, biggerGroup}
			} else {
				newGroups = append(groups[:i-1], smallerGroup, biggerGroup)
			}
			break
		}
	}
	if i < len(groups)-1 {
		newGroups = append(newGroups, groups[i+1:]...)
	}
	return recurse(loc+1, arr, target, newGroups...)
}
 
// 主函数入口
func FindMatchGroup(arr []int, target int) []int {
 
	if len(arr) < 2 {
		return nil
	}
 
	var remain = &Group{}
	for i := 1; i < len(arr); i++ {
		remain.Values = append(remain.Values, [2]int{arr[i], i})
	}
 
	return recurse(0, arr, target, remain)
}