LeetCode(五) 两数之和

代码链接
题目题目链接

两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

有三种解决方案：

1. 暴力法
2. 两遍 Hash
3. 一遍 Hash

方案一： 暴力法

这种方法很简单，通过两重遍历，找到 x + y = target 的 index ，然后将 index 加入数组返回即可

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    
    for i in 0 ..< nums.count {
        for j in  i + 1 ..< nums.count {
            if nums[i] + nums[j] == target {
                return [i,j]
            }
        }
    }
    
    return []
}

复杂度分析：

1. 时间复杂度: O(n²)
2. 空间复杂度: O(1)

这种方案在 LeetCode 的时间限制下是不能通过的。

方案一：两遍 Hash

第一种方案固然可以解决问题，但是时间复杂度太大，所以我们需要降低时间复杂度。一般而言，都是通过空间换时间，所以这里需要一种数据结构可以快速查找到 target - nums[i] 的值是否在 nums 中，字典（hash） 就是最好的数据结构：

1. 首先，通过遍历的方式，将 nums[i] 作为 key ， i 作为 value 添加到字典中 map[Int:Int]
2. 遍历 nums，通过检索 target - nums[i] 是否在 map 中，如果在就直接返回 i 和 map 中的 value

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var map : [Int : Int] = [Int : Int]()
    
    for i in 0 ..< nums.count {
        map[nums[i]] = i
    }

    for  i in 0 ..< nums.count {
        var result = target - nums[i]
        if let temp = map[result] {
                return [i, temp]
        }
    }
    return []
}

复杂度分析：

1. 时间复杂度： O(n)
2. 空间复杂度： O(n)

结果：

方案二：一遍 Hash

上面的方案，我们可以发现，即使一开始 map 没有值，只要我们遍历的时候添加上，后面找到另一个值就会回头对比，所以一遍遍历，一遍向 map 中添加值，然后继续遍历，一次 hash 就可以了

var map : [Int : Int] = [Int : Int]()
 
 for  i in 0 ..< nums.count {
     var result = target - nums[i]
     if let temp = map[result] {
             return [i, temp]
     }
     
     map[nums[i]] = i
 }
 return []

复杂度分析：

1. 时间复杂度： O(n)
2. 空间复杂度： O(n)

结果：