由于自己關于算法方面確實非常薄弱，所以嘗試在LeetCode上刷題，所有代碼均是基于swift實現(xiàn)。（LeetCode上有提交代碼的部分，如果算法復雜度太高是不會通過的，有興趣的可以自己在網(wǎng)站上提交代碼嘗試，就像刷游戲成就一樣）

題目：給定一個整數(shù)數(shù)組和一個目標值，找出數(shù)組中和為目標值的兩個數(shù)。你可以假設每個輸入只對應一種答案，且同樣的元素不能被重復利用。

示例:

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思考：遇到數(shù)組類型的題目，下意識的想到的是遍歷，從第一個元素開始，如第一個元素是2，那么就需要遍歷數(shù)組剩下的元素是否存在一個7，如果不存在，那就繼續(xù)取出第二個元素，獲取結果繼續(xù)遍歷。

復雜度分析：

時間復雜度：O(n^2)O(n?2??)， 對于每個元素，我們試圖通過遍歷數(shù)組的其余部分來尋找它所對應的目標元素，這將耗費?O(n)O(n)?的時間。因此時間復雜度為?O(n^2)O(n?2??)。

空間復雜度：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。（這里說的是最基礎的題目運行時間，但是要遇到非常龐大的數(shù)組且正確結果是數(shù)組最后兩個元素的時候，運行時間非常爆炸。）

（你代碼提交解答的時候，LeetCode會自動替你審核非常方便）

我們設定一個result = 9 - 當前元素

正解：那么是否存在一種方法循環(huán)遍歷一次，即可找出正確答案？既然這里要獲取的元素，返回的結果是數(shù)組的下標，那么字典這種鍵值對結構就可以將每個元素和他的下標一一對應起來。而字典我們可以直接獲取他的allKeys，并且可以直接判斷是否contain某個元素。即遍歷之前我們先定義一個空的字典，遍歷的時候拿到元素，判斷result是否存在于字典的keys里面，如果不存在，那么將當前元素作為key，下標作為value存入此字典，繼續(xù)循環(huán)。

代碼：

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