?2016-2026 Matools All rights reserved,
粵ICP備17059708號(hào)
給定一個(gè)整數(shù)數(shù)組 nums?和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那?兩個(gè)?整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。----來源于leetcode
示例:
給定 nums = [2, 7, 11, 15], target = 9 因?yàn)?nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0,
1]
?下面我們針對(duì)題目進(jìn)行不同方式解答
?
第一種方式:?
暴力法很簡(jiǎn)單,遍歷每個(gè)元素x,并查找是否存在一個(gè)值與target - x 相等的目標(biāo)元素,下面是swift代碼解答,可直接運(yùn)行
class Solution { var nums: [Int] = [1,4,15,16,45,86,9,8,3] let target = 17 var
tempArr= [Int]() func twoSum(_ nums: [Int], _ target: Int) ->[Int]{ for i in
0..<nums.count { for j in i+1..<nums.count { if nums[j] == target - nums[i] {
tempArr.append(i) tempArr.append(j) } } }return tempArr } }
?
第二種方式:
通過一遍哈希表.在進(jìn)行迭代并將元素插入到表中的同時(shí),還會(huì)回頭查看表中是否已經(jīng)存在當(dāng)前元素所對(duì)應(yīng)的目標(biāo)元素.如果存在,那說明找到了對(duì)應(yīng)的解,并立即將其返回.
var nums = [22,44,33,66,3,8,4,99] var target = 88 func twoSum(_ nums: [Int],
_target: Int)-> [Int] { var result = [Int]() var container = Set<Int>() for
(index, value)in nums.enumerated() { let match = target - value if
container.contains(match) { let first= nums.firstIndex(of: match)!
result.append(first) result.append(index)break } container.insert(value) }
return result } let result:[Int] = twoSum(nums, _target: target) print(result)
題解說明:
1. 創(chuàng)建Hash Container解決時(shí)間復(fù)雜度問題
2. 在Hash Container中查找match匹配,
查找成功,找到value和match的索引index
3.查找失敗,將value1存入Hash Container中
4.繼續(xù)遍歷數(shù)組.
?
拓展:Set<Int>() ---為講解
Set講解:
* Set容器是用來存儲(chǔ)相同類型的無序集合,而且元素是不重復(fù)的;
* 存儲(chǔ)在Set中的元素有個(gè)限制: 元素類型必須是Hashable可哈?；?
* 可快速查找
Set與數(shù)組不同的是,Set里面的元素是無序的,并且每個(gè)元素都不能重復(fù).
?
上面就是兩數(shù)之和的題解以及拓展知識(shí)Set的講解,希望對(duì)大家有所幫助.
熱門工具 換一換