兩數(shù)之和
給定一個整數(shù)數(shù)組 nums 和一個目標(biāo)值 target，請你在該數(shù)組中找出和為目標(biāo)值的那兩個整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會對應(yīng)一個答案霉翔。但是，數(shù)組中同一個元素不能使用兩遍苞笨。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路
1债朵、暴力法
暴力法很簡單子眶，雙重for循環(huán)，遍歷每個元素 x序芦，并查找是否存在一個值與 target - x 相等的目標(biāo)元素
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] { // 544ms 13.9MB
for (index, value) in nums.enumerated() {
for remainderIndex in index ..< nums.count {
if ((value + nums[remainderIndex]) == target) && (index != remainderIndex) {
return [index, remainderIndex]
}
}
}
return []
}
}
時間復(fù)雜度為 O(n^2)臭杰，空間復(fù)雜度：O(1)。
2谚中、兩遍字典即哈希表
哈希表渴杆，通過以空間換取速度的方式，我們可以將查找時間從 O(n) 降低到 O(1)藏杖。
一個簡單的實(shí)現(xiàn)使用了兩次迭代。在第一次迭代中脉顿，我們將每個元素的值和它的索引添加到表中蝌麸。然后，在第二次迭代中艾疟，我們將檢查每個元素所對應(yīng)的目標(biāo)元素（target - nums[i]）是否存在于表中来吩。注意，該目標(biāo)元素不能是 nums[i]本身蔽莱！
func twoSum(_ nums: [Int], _ target: Int) -> [Int] { // 56ms 14.1MB
var dict: [Int: Int] = [:]
for (index, value) in nums.enumerated() {
dict[value] = index
}
for (index, value) in nums.enumerated() {
if let remainderIndex = dict[target - value] {
if remainderIndex != index {
return [index, remainderIndex]
}
}
}
return []
}
由于哈希表將查找時間縮短到 O(1) 弟疆，所以時間復(fù)雜度為 O(n)，空間復(fù)雜度：O(n)
3盗冷、一遍哈希表
在進(jìn)行迭代并將元素插入到表中的同時怠苔，可以檢查表中是否已經(jīng)存在當(dāng)前元素所對應(yīng)的目標(biāo)元素。如果它存在仪糖，那找到了對應(yīng)解柑司，并立即將其返回。
以數(shù)組元素值作為key锅劝，存儲對應(yīng)的位置index
func twoSum(_ nums: [Int], _ target: Int) -> [Int] { // 48 ms 14 MB
guard nums.count > 1 else { return [] }
var indexDic: [Int: Int] = [:]
for (index, value) in nums.enumerated() { // 遍歷
if let resetIndex = indexDic[target - value] { // 獲取對應(yīng)元素的位置
return [index, resetIndex]
}
indexDic[value] = index
}
return []
}
dic.keys來判斷是否包含值
func twoSum(_ nums: [Int], _ target: Int) -> [Int] { // 48ms 14MB
var dic: [Int: Int] = [:]
for (index, num) in nums.enumerated() {
let remainder = target - num
if (dic.keys.contains(remainder)) { // 看keys算法包含
if let resetIndex = dic[remainder], resetIndex != index {
return [resetIndex, index]
}
}
dic[num] = index
}
return []
}
只遍歷了包含有 n 個元素的列表一次攒驰，在表中進(jìn)行的每次查找只花費(fèi) O(1) 的時間，空間復(fù)雜度：O(n)
