001_TwoSum.swift

//
// 1.两数之和
//
// 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
// 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
//
// 题目链接：https://leetcode-cn.com/problems/two-sum/
// 标签：数组、哈希表
// 要点：顺序遍历目标数组，利用哈希表（Dictionary）查找元素时间复杂度O(1)的特性，
//      以『元素值』为Key，『元素索引』为Value暂存，暂存字典中若存在target - num的键值对，即命中返回
// 时间复杂度：O(n)
// 空间复杂度：O(n)
//

import Foundation

class Solution {
    typealias Index = Int
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        // 利用哈希表（Dictionary）查找元素时间复杂度O(1)的特性
        var indexesDictionary = [Int: Index]()
        
        for (index, num) in nums.enumerated() {
            // 暂存字典中若存在target - num的键值对，即命中返回
            if let pairIndex = indexesDictionary[target - num] {
                return [pairIndex, index]
            }
            // 以『元素值』为Key，『元素索引』为Value暂存
            indexesDictionary[num] = index
        }
        
        return []
    }
}

// Tests
let s = Solution()
assert(s.twoSum([2,7,11,15], 9) == [0, 1])