- 给一个整型数组和一个目标值，判断数组中是否有两个数字之和等于目标值
分析：
（1）如果每次选中一个数，然后遍历整个数组，判断是否有另一个数使两者之和满足条件。这种时间复杂度为O(n^2)，不是最优解。
（2）在遍历数组的过程中，利用集合保存遍历的当前值。若集合中存在目标值减去当前值的差值，说明数组中一定有一个数与当前值之和等于目标值。这种时间复杂度为O(n)，得到优化。
func twoSum(nums:[Int],_ target:Int) -> Bool {
var set = Set<Int>()
for num in nums {
if set.contains(num) {
return true
}
set.insert(num)
}
return false
}
- 给定一个整型数组中有且仅有两个数字之和等于目标值，求两个数字在数组中的序号
分析：与问题1思路类似，这里采用字典的形式，时间复杂度为O(n)
func twoSum(nums: [Int], _ target: Int) -> [Int] {
var dict = [Int: Int]()
for (i, num) in nums.enumerated() {
if let lastIndex = dict[target - num] {
return [lastIndex, i]
} else {
dict[num] = i
}
}
fatalError("No valid output!")
}
- 虽然不是两数之和的问题，但算法思想类似的问题：字符串中的第一个唯一字符（题目来自LeetCode）
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例: s = "leetcode"，返回 0；s = "loveleetcode",返回 2.
注意事项：您可以假定该字符串只包含小写字母。
class Solution {
func firstUniqChar(_ s: String) -> Int {
var dic = [Character: Bool]()
for char in s {
if let _ = dic[char] {
dic[char] = true
}
else {
dic[char] = false
}
}
for (i,char) in Array(s).enumerated() {
if dic[char]! == false {
return i
}
}
return -1
}
}
