两数之和

1. 题目描述

给出一个整数数组，请在数组中找出两个加起来等于目标值的数， 你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的 假设给出的数组中只存在唯一解 例如： 给出的数组为 {20, 70, 110, 150},目标值为90 输出 index1=1, index2=2

2. 思路

对比和为S的两个数字.md，这个数组没有排序

1. 思路一
   • 暴力法
   • 固定一个数字，遍历查找另一个数字
2. 思路二
   • 遍历一遍放入set中
   • 再遍历一遍查看另一个数字是否再map中

3. 实现

3.1. 暴力法

//时间：O(N²)
//空间：O(1)
func twoSum(numbers []int, target int) []int {
	if len(numbers) == 0 {
		return nil
	}

	res := make([]int, 0)
	for i := 0; i < len(numbers); i++ {
		for j := i + 1; j < len(numbers); j++ {
			if numbers[i]+numbers[j] == target {
				res = append(res, i+1, j+1)
				return res
			}

		}
	}

	return res

}

3.2. map

//时间：O(N)
//空间：O(N)
func twoSum2(numbers []int, target int) []int {
	if len(numbers) == 0 {
		return nil
	}

	res := make([]int, 0)

	m := make(map[int]int, 0)
	for i := 0; i < len(numbers); i++ {
		m[numbers[i]] = i
	}

	for i := 0; i < len(numbers); i++ {
		j, ok := m[target-numbers[i]]
		if j == i {
			continue
		}
		if ok {
			res = append(res, i+1, j+1)
			return res
		}
	}

	return res

}

4. 参考

• 两数之和_牛客题霸_牛客网
• 两数之和 - 两数之和 - 力扣（LeetCode）