两数之和

发表于 分类于 Disqus：

如下，输入一个数组和一个目标变量：

input: [1, 3, 1, 3, 2, 2, 5, -1]

input: 4

要求找到此数组中所有两数之和等于目标变量的元素集合并返回，并且结果中不能有重复项。

思路

遍历数组，将当前元素以及其与目标变量的差值存放入字典中，如果字典中已存在，则将其放入结果集中。遍历完成之后，利用Set 集合去重，最后返回。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func twoSum(_ array: [Int], _ target: Int) -> [[Int]] {
  var dict = [Int: Int]()
  var result = [[Int]]()
  for item in array {
    if let num = dict[item] {
      result.append([num, item])
    }
    dict[target - item] = item
  }
  var resultSet: Set<Int> = []
  for (idx, item) in result.enumerated() {
    if !resultSet.insert(item[0]).inserted && !resultSet.insert(item[1]).inserted {
      result.remove(at: idx)
    }
  }
  return result
}