為了解釋時間跟空間的取捨，來一條leetcode的題目，就是最經典的第一題Two Sum

輸入一組array、數值target，請從array中尋找兩個數字加總是等於tartget，並回傳array對應的index。
(兩個index不可重複、只會有一個答案)

ex 1.
Input: nums = [2,7,11,15], target = 9
Output: [0,1] (nums[0] + nums[1] == 9)

ex 2.
Input: nums = [3,2,4], target = 6
Output: [1,2] (nums[1] + nums[2] == 6)

如果你沒做過這題，強烈建議你先思考一下怎麼解。

防雷
防雷
防雷

最直覺的暴力解
跑兩次迴圈，每一個數值都跟其他數值加總一次
如果剛好等於target就回傳出去
時間複雜度為O(n^2)
註. 你可能會想，如果它剛好在迴圈的前幾次就找到答案了，那時間複雜度還是O(n^2)嗎？
-我們討論時間複雜度都會取最差的case，如果找不到target，這一段程式會完整跑完n*n。

func twoSum(nums []int, target int) []int {
	for i, v := range nums {
		for j, v2 := range nums {
			if i == j {
				continue
			}

			if v+v2 == target {
				return []int{i, j}
			}
		}
	}

	return nil
}

那存在時間複雜度為O(n)的解法嗎?
有的，這時候可以用hash map來解

nums = [2,7,11,15], target = 9
多一個map來記，key存值，val存index
跑一個迴圈，每一個值減去target，如果剛好在map找得到對應的key，那就是答案了。

ex.
index: 0, val: 2, map:{}
map[9-2] // 找不到

把2存到map裡面
map:{
	2: 0,
}

index: 1, val: 7
map[9-7] // 從map找到2 index是0 回傳[0,1]出去

程式:

func twoSum(nums []int, target int) []int {
	hash := make(map[int]int)
	for i, n := range nums {
		if j, ok := hash[target-n]; ok {
			return []int{j, i}
		}

		hash[n] = i
	}

	return nil
}

時間的複雜度從O(n^2)降低為O(n)，但空間複雜度從O(1)升為O(n)。空間換時間或時間換空間，是很常有的情況，像是為了節省撈取DB的時間，所以做快取在記憶體，或者DB多記一些統計的欄位，避免重複的計算。

但是這取捨並非絕對!!如果這題的array有排序過，那會有另外一種解法，時間的複雜為O(n)，但空間複雜度維持O(1)。

明天講！byebye