【Go/Golang】LeetCode Practice - Two Sum

居裡貓最近開起來 LeetCode 的練習之路，接下來不定期的分享練習歷程。

同時練習Go這個語言，如有各路大大有建議還望提攜提攜。

今天要分享的是 Two Sum，我想這個作為練習開端再好不過。

題目連結：1.Two Sum

題目簡易說明：輸入一個整數陣列及一個目標數。

找出陣列中相加等於目標數的陣列索引值。

接下來來看一下解題程式1：

程式碼1

	func TwoSum1(nums []int, target int) []int {
	index := 0
	otherIndex := -1
	for i := 0; i < len(nums); i++ {
	value := target - nums[i]
	for j := 0; j < len(nums); j++ {
	if j == i {
	continue
	} else {
	if nums[j] == value {
	otherIndex = j
	break
	}
	}
	}
	if otherIndex == -1 {
	index += 1
	} else {
	break
	}
	}
	ans := []int{index, otherIndex}
	if otherIndex == -1 {
	return nil
	} else {
	return ans
	}
	}

view raw TwoSumPractice_TwoSum1.go hosted with ❤ by GitHub

程式碼1說起來就是利用兩層迴圈去搜尋我們所要的答案，

這樣確實可以找得出解，但因為迴圈遍歷所有陣列會產生大量的時間花費，

因此有了第二種解題方式。

程式碼2

	func TwoSum2(nums []int, target int) []int {
	var dic = make(map[int]int)
	for i := 0; i < len(nums); i++ {
	if v, ok := dic[target-nums[i]]; ok {
	return []int{v, i}
	} else {
	dic[nums[i]] = i
	}
	}
	return nil
	}

view raw TwoSumPractice_TwoSum2.go hosted with ❤ by GitHub

程式碼2利用了map的技巧，在一層迴圈遍歷陣列的同時將陣列該數值設為key，

並將索引寫入value，而在下一次迴圈時去map中找尋是否有答案。

因為這樣的作法可以少去一層迴圈的工作，等於降低大量的時間花費。

而map在找尋是否存在指定key資訊會透過hash table來運算，

所以這個時間花費並不像迴圈般的高。（詳細還請自行研究Hash相關資訊。

結論

從本次練習可以知道，解題的方式有很多種，

但如果想要尋求高效的解題方式，確實還是需要一些想法，

如何利用較少的資源解決問題。

而此練習同時也學習了一些Go的程式技巧。

希望本次分享大家會喜歡，如果有什麼建議歡迎留言與我分享。