两数之和

题目

题目来源,https://leetcode-cn.com/problems/two-sum

给定一个整数数组 nums 和一个目标值 target,在数组中找出和为目标值的那两个整数,返回他们的数组下标。

假设每种输入只会对应一个答案。但同一个元素不能使用两次。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1
2
3
4

Go 语言实现

双重遍历

思路双重遍历确认两个数之和为 target 即可。注意第二个数从第一个数的后面元素遍历即可。

func TwoSum1(nums []int, target int) []int {
	// # 双重遍历
	//O(n^2), O(1)
	l := len(nums)
	for i, a := range nums {
		// 计算 当前元素和后续元素的和进行比较
		for j:=i+1; j<l; j++ {
			if a + nums[j] == target {
				return []int{i, j}
			}
		}
	}
	return []int {}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

使用 map 存储补数

补数:若 a + b = target,那么在 target 下 a 和 b 互为补数。

思路,使用 map 结构,存储 key 为遍历值的 补数,而值对应值的索引。遍历时,判断是否存在该数的补数,若存在,找到答案!

func TwoSum2(nums []int, target int) []int {
	// # map 结构,在 map 中保存 补数 进行测试
	// O(N), O(N)
	vIdx := map[int]int{}
	for i, n := range nums {
		// 判断 n 的补数是否存在
		if idx, exists := vIdx[n]; exists {
			if i < idx {
				return []int {i, idx}
			} else {
				return []int {idx, i}
			}
		}
		// 以补数作为 key 存储补数及对应的索引
		vIdx[target - n] = i
	}
	return []int {}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

本题来自于 Leetcode,在提交中表现如下:

执行用时 :4 ms, 在所有 golang 提交中击败了97.39%的用户

内存消耗 :3.7 MB, 在所有 golang 提交中击败了45.21%的用户