【LeetCode通關(guān)全記錄】1. 兩數(shù)之和
題目地址：1. 兩數(shù)之和
解法1：暴力枚舉（時(shí)間換空間）
估計(jì)所有人看到這道題想到的第一個(gè)方法都是暴力枚舉旬薯，即對(duì)數(shù)組中的每一個(gè)數(shù)都遍歷一次該數(shù)組烧给，尋找是否有滿足num1 + num2 == target的數(shù)子刮。這種方法比較簡(jiǎn)單，是一種用時(shí)間換空間的方法双肤。
func twoSum(nums []int, target int) []int {
if nums == nil {
return []int{}
}
for index1, num1 := range nums {
for index2, num2 := range nums {
if num1 + num2 == target && index1 != index2 {
return []int{index1, index2}
}
}
}
return []int{}
}
執(zhí)行用時(shí): 16 ms（超過(guò)57%的Golang提交記錄）
內(nèi)存消耗: 4.6 MB（超過(guò)91%的Golang提交記錄）
時(shí)間復(fù)雜度：O(n^2)项阴，對(duì)數(shù)組中的每一個(gè)數(shù)都需要遍歷兩次數(shù)組吁断，所以算法的執(zhí)行時(shí)間與問(wèn)題規(guī)模為平方關(guān)系炮障；
空間復(fù)雜度：O(1)，只使用了常數(shù)個(gè)數(shù)的存儲(chǔ)空間伊者。
解法2：哈希表（空間換時(shí)間）
除了暴力枚舉之外英遭，還有一種不太好想到的方法：用空間換時(shí)間。我們可以邊遍歷數(shù)組邊將數(shù)組元素num作為key亦渗、num的下標(biāo)作為value放入哈希表中挖诸，如果在之后的遍歷中遇到target - num在哈希表中的情況，說(shuō)明找到了滿足要求的數(shù)法精，直接返回遍歷到的數(shù)據(jù)的下標(biāo)和該key對(duì)應(yīng)的value即可多律。注意要先比較再插入哈希表，以此避免num和自身比較亿虽。
func twoSum(nums []int, target int) []int {
if nums == nil {
return []int{}
}
t := make(map[int]int)
for index, num := range nums {
if i, ok := t[target-num]; ok {
return []int{i, index}
}
t[num] = index
}
return []int{}
}
執(zhí)行用時(shí): 4 ms（超過(guò)98%的Golang提交記錄）
內(nèi)存消耗: 4.2 MB（超過(guò)35%的Golang提交記錄）
時(shí)間復(fù)雜度：O(n)菱涤，只需要遍歷一次數(shù)組苞也；
空間復(fù)雜度：O(n)洛勉，哈希表的長(zhǎng)度與問(wèn)題規(guī)模成正比。
