未分類

Two Sum

Array, Go, HashTable, LeetCode

Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Exmaple:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
提示 解題應用
Hash Table Hash Map
Array Array/Slice

Default:

1
2
func twoSum(nums []int, target int) []int {
}

解答思路:

剛開始看到題目的時候因為沒有細想，單純從提示來看的話我馬上就往錯誤的方向解答，使得一開始寫的很糟
最初的想法是例用 nums[key]%target 取餘數的方式來為hashtable做分類，整除就放進Array[index]為0的位置，餘1就放進index為1以此類推，當然這樣做也是個方式但是target有可能是0，也就產生了分母為0而error的情況，此外就算是前述解決還有負數的情況要考量， 1%8=1 但是 1%-8=-7 為了要解上述問題只會讓無關的code越做越糟，所以倒不如用減的，將 target-nums[key] 不過這麼一來就沒辦法用index來做為分類(bucket)的依據，因為數字會很大所以就改用Map的方式來實現。

程式碼解說:

這邊我特別用struct來將當前nums的資料做儲存，不這麼做的話經由array分類之後就算已經知道了哪組數字合可以得到結果，但是結果需要的是你回傳該值於nums的index，總不能再將這組數字再拿到nums做搜尋也太浪費時間。

1
2
3
4
type hash struct {
	index int
	value int
}

這邊要注的是在Go語言中，如果初始化資料有巢狀的情況，好比map裡頭又有map或是map裡頭有array等等的話，在Go只初始化了最外層，也就是說你必需要在當需要使用內層的時候，寫一個判斷式來確定裡頭是不是分配了空間，沒有的話就要再對裡頭make一次。

1
2
3
4
5
hashTable := make(map[int][]hash)
_, ok := hashTable[k]
if !ok {
	hashTable[k] = make([]hash, 0)
}

最後可能會遇到一種狀況是進來的資料有重覆，好比target是0有可能nums裡面有兩個0，所以在上一點我初始化資料時每個map裡頭才又包了array，不過因為題目有明確的說明只有一組結果的關係，所以這種重覆的值如果剛好又是結果的話，在array裡頭肯定長度是2，雖然我還是用 len(value) 來判斷，不過敘述就直接指明該index了

1
2
3
4
5
6
7
8
9
if ok && key != target-key {
	result[0] = value[0].index
	result[1] = v[0].index
	break
} else if ok && len(value) > 1 {
	result[0] = value[0].index
	result[1] = value[1].index
	break
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func twoSum(nums []int, target int) []int {
	type hash struct {
		index int
		value int
	}
	hashTable := make(map[int][]hash)
	result := make([]int, 2)
	for key, value := range nums {
		k := target - value
		_, ok := hashTable[k]
		if !ok {
			hashTable[k] = make([]hash, 0)
		}
		hashTable[k] = append(hashTable[k], hash{key, value})
	}
	for key, value := range hashTable {
		v, ok := hashTable[target-key]
		if ok && key != target-key {
			result[0] = value[0].index
			result[1] = v[0].index
			break
		} else if ok && len(value) > 1 {
			result[0] = value[0].index
			result[1] = value[1].index
			break
		}
	}
	return result
}

總結:

若在一串無序數字中需要找一組數字，且此組數字有一定的1對1關係
用HashTable來分類實作。

分享到