iT邦幫忙

2021 iThome 鐵人賽

DAY 18
1
自我挑戰組

30 天學 Golang?Go 啦哪次不 Go系列 第 18

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 練習就到這邊結束,有任何問題都歡迎與我告知 :)
本篇文章同步發佈於我的部落格


上一篇
Day17# panic & recover
下一篇
Day19# Leetcode - Palindrome Number
系列文
30 天學 Golang?Go 啦哪次不 Go20

尚未有邦友留言

立即登入留言