1. 两数之和 [Array] [Easy]

题目链接

https://leetcode-cn.com/problems/two-sum/

题目描述

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

边界条件：

至少需要两个值，所以如果数组元素少于 1 则不合法。

1. 两次循环

两次循环取出对应的值，判断相加是否等于 target，然后取出即可。

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        guard nums.count > 1 else { return [] }
        for i in 0...(nums.count - 2) {
            for j in (i + 1)...(nums.count - 1) {
                if nums[i] + nums[j] == target { return [i, j] }
            }
        }
        return []
    }
}

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

2. 字典

1. 遍历数组，取出当前坐标的值 a。
2. 用 targe 减去 a，则为另一个整数 b。
3. 如果 b 在字典中存在，则取出 b 对应的 value。
4. 如果不存在，则把 a 作为 key，a 的坐标作为 value 存入字典中。

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    guard nums.count > 1 else { return [] }
    var dict = [Int: Int]()
    for (i, a) in nums.enumerated() {
        if let j = dict[target - a] { return [j, i] }
        dict[a] = i
    }
    return []
    }
}

• 时间复杂度：O(n)
• 空间复杂度：O(n²)