1. Two Sum_Swift

难度

简单

题目

在给定的数组中找出一组特定的数字，使其和等于一个给定的值，并返回这组数字的索引。
Example 如下：

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路

思路一

通过二次遍历筛选符合条件的一组数字，时间复杂度为O(n²)。

思路二

运用 hash 表，对于每个数先看和为 target 所需的数是否在 dict 内，如果已经在则直接返回，否则才把自身放进 dict 里。时间复杂度为 O(n)。

代码

方法一

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

    return [-1, -1]
}

方法二

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var targetDic = [Int: Int]()

    for (index, num) in nums.enumerated() {
        guard let targetIndex = targetDic[target - num] else {
            targetDic[num] = index
            continue
        }
        return [targetIndex, index]
    }

    return [-1, -1]
}