一、前言

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

开始我的思路是这样的：

1. 判断数组的count是否小于2，如果小于2则直接返回一个空数组
2. 这里假设数组参数名为nums,设定两个变量start和end，start初始为0,end为nums.cout - 2，当strat <= end的时候进行循环，nums[start]分别尝试与nums[start + 1]...nums[nums.count - 1]相加，如果等于目标值，则返回对应的索引数组，如果不等于目标值则继续循环，每次循环完成后将start值加1。
3. 遍历完成之后仍没有结果的话则返回一个空数组

代码如下：

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上新建了一个仓库，作为我刷题的记录，大家有兴趣的话也可以去看看。

GitHub地址：https://github.com/BreadAwesome/LeetCode-Swift