算法：两数之和 | Stellar Wake

Open Table of contents

题目
方法一：暴力遍历
- 算法思路总结
方法二：借助字典高效遍历
- 算法思路总结

题目

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

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

方法一：暴力遍历

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 []
}

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

外层循环（枚举所有数字及其索引）
```
for (i, num) in nums.enumerated() {
```
这一层循环遍历数组 nums 中的每个元素，并记录下当前元素 num 以及对应的索引 i。
计算补数
```
let complement = target - num
```
对于当前元素 num，通过 target - num 计算得到另一个数（称为补数，即 complement），其作用是希望能与 num 组合起来使其和为 target。
内层循环（再次遍历数组查找补数）
```
for (j, otherNum) in nums.enumerated() where i != j {
```
这一层循环再次遍历整个数组，寻找满足条件的另一个数字 otherNum。注意，这里使用了 where i != j 条件，确保不会使用同一个元素两次。
检查是否找到匹配的补数
```
if otherNum == complement {
    return [i, j]
}
```
如果在内层循环中发现 otherNum 等于之前计算的 complement，则说明找到了两个数，它们的和等于 target。此时，函数会立即返回一个包含这两个索引 [i, j] 的数组。
没有找到匹配时返回空数组
```
return []
```
如果完成所有循环后都没有找到符合条件的一对数字，则返回一个空数组，表示不存在满足条件的两个数。

算法思路总结

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

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

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 []
}

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

下面详细解释各个步骤：

初始化哈希表 定义一个字典 dict，键是数组中的数值，值是相应的索引：
```
var dict = [Int: Int]()
```
遍历数组并查找匹配 使用 enumerated() 方法遍历数组，使得在每一步可以同时获得元素的索引和值：
```
for (index, value) in nums.enumerated() {
```
- 对于当前值 value，计算其所需的匹配数，即 target - value。
- 在字典中查找这个匹配数：
```
if let otherIndex = dict[target - value] {
    return [otherIndex, index]
}
```
  如果找到了匹配的索引 otherIndex，说明已经遍历过的某个数 nums[otherIndex] 和当前数 value 之和正好等于目标值 target，于是返回这两个索引。
更新字典 如果没有找到匹配值，则将当前值以及对应的索引添加到字典中：
```
dict[value] = index
```
这样，当后续的数字需要一个与之配对的数字时，就可以在字典中快速查找。
返回结果 如果遍历完整个数组都没有找到满足条件的两个数，则返回空数组：
```
return []
```

算法思路总结

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