LeetCode 1. 两数之和 Two Sum

【题目描述】
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

【示例】

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

【思路1】
1、暴力解
2、变量两遍 每两个元素相加 和是不是等于目标值
3、时间复杂度O(n^2)
4、空间复杂度O(n)

Swift代码实现：

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

【思路2】
1、使用哈希表
2、把每个数字和以及它的index 保存到map
3、每次遍历使用target-num，如果存在map[target-num]下标值 说明 已保存的值+当前值=目标值target
4、时间复杂度O(n)
5、空间复杂度O(n)

Swift代码实现：

func twoSum2(_ nums: [Int], _ target: Int) -> [Int] {
    var map = [Int:Int]()
    for (i,num) in nums.enumerated() {
        if let index = map[target-num] {
            return [index,i]
        }
        map[num] = i
    }
    return []
}