Top Page

read

今天要刷的題目是 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 練習就到這邊結束,有任何問題都歡迎與我告知 :)

Blog Logo

yuchan


Published