每天一道LeetCode题——两数之和每天一道LeetCode题——两数之和

前言
算法有多重要，不用多说。和之前学习设计模式一样，现在每天开始刷（bei）题(nue)，并记录下答题思路和过程，希望这个系列能坚持吧。
题目
两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

【每天一道LeetCode题——两数之和】示例
给定 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.sizefor(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.sizeval cache = HashMap()//缓存数组中的值(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 }