2Sum算法

2019-11-07  本文已影响0人  async丶
给一个整型数组和一个目标值,判断数组中是否有两个数字之和等于目标值。

这道题是传说中经典的 “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!")
}
上一篇 下一篇

猜你喜欢

热点阅读