算法：两数之和

发表于 分类于 Disqus：

题目

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

方法一：暴力遍历

1
2
3
4
5
6
7
8
9
10
11
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
  for (i, num) in nums.enumerated() {
    let complement = target - num
    for (j, otherNum) in nums.enumerated() where i != j {
      if otherNum == complement {
        return [i, j]
      }
    }
  }
  return []
}

下面逐行解释这段代码的思路：

  1. 外层循环（枚举所有数字及其索引） 

    1
    for (i, num) in nums.enumerated() {

    这一层循环遍历数组 nums 中的每个元素，并记录下当前元素 num 以及对应的索引 i。

  2. 计算补数 

    1
    let complement = target - num

    对于当前元素 num，通过 target - num 计算得到另一个数（称为补数，即 complement），其作用是希望能与 num 组合起来使其和为 target。

  3. 内层循环（再次遍历数组查找补数） 

    1
    for (j, otherNum) in nums.enumerated() where i != j {

    这一层循环再次遍历整个数组，寻找满足条件的另一个数字 otherNum。注意，这里使用了 where i != j 条件，确保不会使用同一个元素两次。

  4. 检查是否找到匹配的补数 

    1
    2
    3
    if otherNum == complement {
        return [i, j]
    }

    如果在内层循环中发现 otherNum 等于之前计算的 complement，则说明找到了两个数，它们的和等于 target。此时，函数会立即返回一个包含这两个索引 [i, j] 的数组。

  5. 没有找到匹配时返回空数组 

    1
    return []

    如果完成所有循环后都没有找到符合条件的一对数字，则返回一个空数组，表示不存在满足条件的两个数。

算法思路总结

  • 暴力解法：代码使用了暴力法，两层枚举，每次将数组中任意两个不同的元素配对，判断其和是否等于目标值 target。
  • 时间复杂度：由于使用了嵌套循环，最坏情况下需要检查所有可能的两个数字组合，时间复杂度为 O(n²)。（其中 n 为数组长度）
  • 空间复杂度：只使用了常数级别的额外空间，因此空间复杂度为 O(1)。

方法二：借助字典高效遍历

1
2
3
4
5
6
7
8
9
10
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
  var dict = [Int: Int]()
  for (index, value) in nums.enumerated() {
    if let otherIndex = dict[target - value] {
      return [otherIndex, index]
    }
    dict[value] = index
  }
  return []
}

这个算法是一种解决“两数之和”问题的高效方法，主要利用了哈希表（字典）的查找特性来实现，在一次遍历数组的过程中就能找到答案。

下面详细解释各个步骤：

  1. 初始化哈希表
    定义一个字典 dict，键是数组中的数值，值是相应的索引：

    1
    var dict = [Int: Int]()

  2. 遍历数组并查找匹配
    使用 enumerated() 方法遍历数组，使得在每一步可以同时获得元素的索引和值：

    1
    for (index, value) in nums.enumerated() {
    • 对于当前值 value，计算其所需的匹配数，即 target - value。
    • 在字典中查找这个匹配数：
      1
      2
      3
      if let otherIndex = dict[target - value] {
          return [otherIndex, index]
      }
      如果找到了匹配的索引 otherIndex，说明已经遍历过的某个数 nums[otherIndex] 和当前数 value 之和正好等于目标值 target，于是返回这两个索引。

  3. 更新字典
    如果没有找到匹配值，则将当前值以及对应的索引添加到字典中：

    1
    dict[value] = index

    这样，当后续的数字需要一个与之配对的数字时，就可以在字典中快速查找。

  4. 返回结果
    如果遍历完整个数组都没有找到满足条件的两个数，则返回空数组：

    1
    return []

算法思路总结

  • 利用哈希表（字典）实现：在一次遍历数组的过程中，利用字典来记录已经遍历过的数字及其索引。
  • 查找补数：对于当前数字，计算补数（即 target 减去当前数字），然后检查字典中是否存在这个补数。若存在，则说明找到了满足条件的两个数字。
  • 时间复杂度：只需一次遍历，每次查找与插入操作均为 O(1)，整体时间复杂度为 O(n)。（其中 n 为数组长度）
  • 空间复杂度：需要额外使用一个字典存储数字及其索引，因此空间复杂度为 O(n)。（最坏情况字典大小与数组长度相同）