题目描述

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

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

示例:

给定nums = [2, 7, 11, 15] target = 9
返回索引[0, 1]

首先想到的就是暴力方法，即使用两个for循环，遍历两次数组，看有没有和是目标值的。显然这样时间复杂度太大，O(n*n)

哈希表为此构建目的: 通过以空间换取时间方式,我们可以查找时间从O(n)降低到O(1).近似恒定时间快速查找,我用”近似”来描述,是因为一旦出现冲突,哈希表的查找时间可能会退化到O(n).

原理:使用两次迭代,第一次迭代将每个元素的值作为字典的key和索引作为字典的value添加到表(就是字典) 第二次迭代,检查每个元素对应的目标元素是否存在于表中

// 耗时约:20ms [11, 2, 7, 15] 9
func twoSum1(nums: [Int], target: Int) -> [Int] {
    
    var dict: [Int : Int] = [Int : Int]()
    for (index, item) in nums.enumerated() {
        // 值作为字典索引,index作为字典的value
        dict[item] = index
    }
    print(dict) // [7: 2, 2: 1, 15: 3, 11: 0]
    
    for (index, item) in nums.enumerated() {
        let complement = target - item
        if let complementIndex = dict[complement]{
            if complementIndex == index{
                continue
            }else{
                return [index, complementIndex] // [1, 2]
            }
        }
    }
    return []
}

在进行迭代并将元素插入到表中的同时,可以回过头来检查表中是否已经存在当前元素所对应的目标元素.如果它存在,就立即返回

// 耗时约:16ms
func twoSum2(nums: [Int], target: Int) -> [Int] {
    var table: [Int : Int] = [Int : Int]()
    for (i, num) in nums.enumerated() {
        let res: Int = target - num
        print(table)
        if let secondIndex = table[res]{
            return [secondIndex, i]
        }else{
            // 值作为字典索引,i作为字典的value
            table[num] = i
        }
    }
    return [0, 0]
}

难点:值作为字典索引,i作为字典的value 时间复杂度为O(n)