Leetcode001-Two Sum（两数之和）

题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

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

受排名第一的题解（力扣 (LeetCode)：官方题解）而作，重复理解大佬们的想法
然后翻译成swift，记录以飨读者。

//方法一：穷举

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

/*
方法二：利用字典特性，通过key来判断value是否存在，key为数组各元素的值，value为元素对应下标
*/

    func twoSumHashtable(_ nums: [Int], _ target: Int) -> [Int] {
        var hashmap: [Int: Int] = [Int: Int]()
        for i in 0..<nums.count {
            hashmap[nums[i]] = i
        }
        
        for i in 0..<nums.count {
            let dif = target - nums[i]
            
            if hashmap[dif] != nil && hashmap[dif] != i {
                return [i, hashmap[dif]!]
            }
        }
        
        return [0]
    }

/*
方法三：一次遍历。这个 一次遍历 很妙啊，两数之和，第一个一定会错过，但第二个不会。
本人适当做了优化，hashmap[dif]直接判断是否有值，由于是线性操作，时间复杂度O(1)，
原作者的containkey方法内部实现应该是一个循环O(n)。
*/

    func twoSumHashtable2(_ nums: [Int], _ target: Int) -> [Int] {
        var hashmap: [Int: Int] = [Int: Int]()
        let size: Int = nums.count
        
        for i in 0..<size {
            let dif = target - nums[i]
            if hashmap[dif] != nil && hashmap[dif] != i {
                return i > hashmap[dif]! ? [hashmap[dif]!, i] : [i, hashmap[dif]!]
            } else {
                hashmap[nums[i]] = i
            }
        }
        
        return [0]
    }

下面的一种解法最常见的：

//首先创建一个hash表，遍历数组以数组value为hash的key，角标index为hash的value
// 最后在头部判断每次用数组target-value去hash表中取值，如果有值，则返回hash表取出值
//和当前角标数组即[lastIndex, index]

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var dict = [Int: Int]()
  
        for (index, value) in nums.enumerated() {
            if let lastIndex = dict[target - value] {
                return [lastIndex, index]
            }
    
            dict[value] = index
        }
  
        fatalError(“No valid outputs”)
    }
}