一、前言
LeetCode也支持Swift了，离职在家，闲来无事，便想着刷几道玩玩，既可以学习一下算法，又可以保持自己的编程状态。
二、Problem
Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
问题的意思是给一个整数数组，再给一个目标值，找出数组中相加等于目标值的两个数，然后将它们的索引作为一个新的数组返回。这里假设只有一个解决方案，也就是说不存在会有两组数相加等于目标值。
三、Solution
开始我的思路是这样的：
- 判断数组的count是否小于2，如果小于2则直接返回一个空数组
- 这里假设数组参数名为nums,设定两个变量start和end，start初始为0,end为nums.cout - 2，当strat <= end的时候进行循环，nums[start]分别尝试与nums[start + 1]...nums[nums.count - 1]相加，如果等于目标值，则返回对应的索引数组，如果不等于目标值则继续循环，每次循环完成后将start值加1。
- 遍历完成之后仍没有结果的话则返回一个空数组
代码如下：
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
if nums.count < 2 {
return [Int]()
}
var start = 0
let end = nums.count - 2
while start <= end {
let firstNum = nums[start]
for (index, secondNum) in nums[(start + 1)..<nums.count].enumerated() {
if firstNum + secondNum == target {
return [start, start + 1 + index]
}
}
start += 1
}
return [Int]()
}
}
提交之后
发现有一个case超时了，确实当数组数量很多的时候需要遍历很多次，这样会花费很多的时间。
数组就不贴出来了，我只知道当我复制进去的时候连Xcode都为之一卡。
那么有什么好的办法可以减少时间耗费呢？
我去看了下这个问题的Discuss，发现了一种很好的思路，那就是使用字典。只需遍历一次，将遍历得到的(index, value)的value作为键，index作为值，然后每次查找时判断目标值 - value这个键在字典中是否存在即可。
代码如下：
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var map = [Int: Int]()
var resultArray = [Int]()
for (index, value) in nums.enumerated() {
if let firstIndex = map[target - value] {
resultArray.append(firstIndex)
resultArray.append(index)
break
}else {
map[value] = index
}
}
return resultArray
}
}
不得不说思路的转变节省了大量的时间，程序员也要学习算法啊。
我在GitHub上新建了一个仓库，作为我刷题的记录，大家有兴趣的话也可以去看看。
