Day18# Leetcode TwoSum

接下来的 12 天，会用每天刷 leetcode 练习的方式来练习 Go
那麽话不多说，我们就进入正题吧 ─=≡Σ(((っﾟ∀ﾟ)っ！

今天要刷的题目是 Leetcode Easy -- twoSum！（登灯）
先来看看题目：

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

要找出阵列内哪两个元素相加起来会是 target 的值，并且用阵列的方式印出这两个元素的 index。

一开始以会动就好的麻瓜心态，来个两次 for 回圈：

func twoSum(nums []int, target int) []int {
	for i, num := range nums {
		for i2, num2 := range nums {
			if i != i2 && num+num2 == target {
				return []int{i, i2}
			}
		}
	}
	return nil
}

但发现 runtime 跑了 56ms 似乎时间有点长...?

竟然只比 7% 的人快XD

稍微参考一下其他人的做法，原来可以透过把 value 及 index 以 map 的方式记录起来，再以回圈的方式确认 target 减掉阵列的元素後的值，是否有包含在 map 内：

func twoSum(nums []int, target int) []int {
	m := make(map[int]int)
	for i, n := range nums {
		idx, ok := m[target-n]
		if ok {
			return []int{idx, i}
		}
		m[n] = i
	}
	return nil
}

嘿，runtime 进步到 4ms 了！
而且使用 map 的方式，就不需要去过滤掉同样的值是否有被重复使用的问题。

其实开始写 Leetcode 才发现我根本对所有的文法都没有很熟悉，例如 idx, ok := m[target-n]，ok 会去得到 m map 内到底有没有这个 key 的存在。

结尾

第一天的 leetcode 练习就到这边结束，有任何问题都欢迎与我告知 :)
本篇文章同步发布於我的部落格