2Sum算法

给一个整型数组和一个目标值，判断数组中是否有两个数字之和等于目标值。

这道题是传说中经典的 “2Sum”，我们已经有一个数组记为 nums，也有一个目标值记为 target，最后要返回一个 Bool 值。

最粗暴的方法就是每次选中一个数，然后遍历整个数组，判断是否有另一个数使两者之和为 target。这种做法时间复杂度为 O(n^2)。

采用集合可以优化时间复杂度。在遍历数组的过程中，用集合每次保存当前值。假如集合中已经有了目标值减去当前值，则证明在之前的遍历中一定有一个数与当前值之和等于目标值。这种做法时间复杂度为 O(n)，代码如下

func twoSum(nums: [Int], _ target: Int) -> Bool {
  var set = Set<Int>()

  for num in nums {
    if set.contains(target - num) {
      return true
    }

    set.insert(num)
  }

  return false
}

如果把题目稍微修改下，变为

给定一个整型数组中有且仅有两个数字之和等于目标值，求两个数字在数组中的序号

思路与上题基本类似，但是为了方便拿到序列号，我们采用字典，时间复杂度依然是 O(n)。代码如下。

func twoSum(nums: [Int], _ target: Int) -> [Int] {
  var dict = [Int: Int]()

  for (i, num) in nums.enumerated() {
    if let lastIndex = dict[target - num] {
      return [lastIndex, i]  
    } else {
      dict[num] = i
    }
  }

  fatalError("No valid output!")
}