前言
算法有多重要，不用多说。和之前学习设计模式一样，现在每天开始刷（bei）题(nue)，并记录下答题思路和过程，希望这个系列能坚持吧。
题目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解法
- 暴力法
最容易想到的思路就是双重遍历数组，直到在数组中找到两个数，它们的和等于目标值即可。
fun twoSum(nums: IntArray, target: Int): IntArray {
val result = IntArray(2)
val length = nums.size
for(i in 0 until length) {
for(j in i+1 until length){
if(nums[i] + nums[j] == target) {
result[0] = i
result[1] = j
break
}
}
}
return result
}
但是这种解法时间复杂度太高了，达到了O(n^2)。想办法降低时间复杂度，减少多余重复的遍历才是重要的。
我们发现，当i从数组第0个遍历到数组最后一个的时候，j一直在重复遍历数组中的数字。这些遍历都是不必要的，重复的。因为只要一次遍历，我们就能知道数组中都有哪些数。
用空间换时间，将数组中的数字和下标缓存到Map中。于是就有了改良之后的解法：Map缓存法。
- Map缓存法
既然我们缓存了数组中的数字和下标，我们就不需要内层循环去寻找另一个加数。直接一次遍历，目标值与当前值的差值如果在Map中，说明之前的遍历有这个加数，直接返回下标即可。反之，则将当前值缓存到Map中，方便之后的遍历。
fun twoSum(nums: IntArray, target: Int): IntArray {
val result = IntArray(2)
val length = nums.size
val cache = HashMap<Int, Int>()//缓存数组中的值(key)和下标(value)
for (i in 0 until length) {
val current = nums[i]
val diff = target - current
if (cache.containsKey(diff)) {
val key = cache[diff]
if (key != null) {
result[0] = key
result[1] = i
break
}
} else {
cache[current] = i
}
}
return result
}
