由于自己关于算法方面确实非常薄弱，所以尝试在LeetCode上刷题，所有代码均是基于swift实现。（LeetCode上有提交代码的部分，如果算法复杂度太高是不会通过的，有兴趣的可以自己在网站上提交代码尝试，就像刷游戏成就一样）
题目：给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思考：遇到数组类型的题目，下意识的想到的是遍历，从第一个元素开始，如第一个元素是2，那么就需要遍历数组剩下的元素是否存在一个7，如果不存在，那就继续取出第二个元素，获取结果继续遍历。
复杂度分析：
时间复杂度：O(n^2)O(n2)， 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n)O(n) 的时间。因此时间复杂度为 O(n^2)O(n2)。
空间复杂度：O(1)O(1)。即时我们在遍历时将前面取过的元素去除，复杂度也非常高。
示例代码：
func twoSum(_nums: [Int],_target:Int) -> [Int] {
//复杂度很高
var array : Array = []
for i : Int in 0 ..< nums.count {
let result : Int = target - nums[i]
var arr = nums
arr.remove(at: i)
if arr.contains(result) {
let c = i+1
var d : Int = 0
for j : Int in c ..< nums.count {
if nums[j] == result {
d = j
break
}
}
array = [i,d]
break
}
}
return array
}
此代码是我最初想到的笨办法……LeetCode提交后，给的运行时间16ms。（这里说的是最基础的题目运行时间，但是要遇到非常庞大的数组且正确结果是数组最后两个元素的时候，运行时间非常爆炸。）
（你代码提交解答的时候，LeetCode会自动替你审核非常方便）
我们设定一个result = 9 - 当前元素
正解：那么是否存在一种方法循环遍历一次，即可找出正确答案？既然这里要获取的元素，返回的结果是数组的下标，那么字典这种键值对结构就可以将每个元素和他的下标一一对应起来。而字典我们可以直接获取他的allKeys，并且可以直接判断是否contain某个元素。即遍历之前我们先定义一个空的字典，遍历的时候拿到元素，判断result是否存在于字典的keys里面，如果不存在，那么将当前元素作为key，下标作为value存入此字典，继续循环。
代码：
var dic : Dictionary = [:]
vararr :Array = []
fori :Intin0..< nums.count{
letcurrent = nums[i]
letresult = target - nums[i]
ifdic.keys.contains(result) {
arr = [dic[result]!,i]
break
}
dic[current] = i
}
return arr
网友评论