Day.3 天秤的两端

为了解释时间跟空间的取舍，来一条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