前言
本題為 LeetCode 前 100 高頻題
我們社區(qū)陸續(xù)會(huì)將顧毅（Netflix 增長(zhǎng)黑客，《iOS 面試之道》作者参萄，ACE 職業(yè)健身教練卫枝。）的 Swift 算法題題解整理為文字版以方便大家學(xué)習(xí)與閱讀。
LeetCode 算法到目前我們已經(jīng)更新到 127 期讹挎，我們會(huì)保持更新時(shí)間和進(jìn)度（周一校赤、周三、周五早上 9:00 發(fā)布）筒溃，每期的內(nèi)容不多马篮，我們希望大家可以在上班路上閱讀，長(zhǎng)久積累會(huì)有很大提升怜奖。
不積跬步浑测，無(wú)以至千里；不積小流，無(wú)以成江海迁央，Swift社區(qū) 伴你前行掷匠。如果大家有建議和意見(jiàn)歡迎在文末留言，我們會(huì)盡力滿(mǎn)足大家的需求岖圈。
難度水平：中等
1. 描述
給定一個(gè)未排序的整數(shù)數(shù)組 nums 讹语，找出數(shù)字連續(xù)的最長(zhǎng)序列（不要求序列元素在原數(shù)組中連續(xù)）的長(zhǎng)度。
請(qǐng)你設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(n) 的算法解決此問(wèn)題蜂科。
2. 示例
示例 1
輸入：nums = [100,4,200,1,3,2]
輸出：4
解釋?zhuān)鹤铋L(zhǎng)數(shù)字連續(xù)序列是 [1, 2, 3, 4]顽决。它的長(zhǎng)度為 4。
示例 2
輸入：nums = [0,3,7,2,5,8,4,6,0,1]
輸出：9
約束條件：
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9
3. 答案
class LongestConsecutiveSequence {
func longestConsecutive(_ nums: [Int]) -> Int {
var set = Set<Int>(nums), longest = 0
for num in nums {
var currentLength = 1
dfs(num, &set, &longest, ¤tLength)
}
return longest
}
private func dfs(_ num: Int, _ set: inout Set<Int>, _ longest: inout Int, _ length: inout Int) {
if !set.contains(num) {
return
}
longest = max(longest, length)
set.remove(num)
length += 1
dfs(num + 1, &set, &longest, &length)
dfs(num - 1, &set, &longest, &length)
}
}
- 主要思想：在 set 的幫助下导匣，迭代數(shù)組并檢查所有鄰居的數(shù)字才菠。
- 時(shí)間復(fù)雜度： O(n)
- 空間復(fù)雜度： O(n)
該算法題解的倉(cāng)庫(kù)：LeetCode-Swift
點(diǎn)擊前往 LeetCode 練習(xí)
關(guān)于我們
我們是由 Swift 愛(ài)好者共同維護(hù)，我們會(huì)分享以 Swift 實(shí)戰(zhàn)贡定、SwiftUI赋访、Swift 基礎(chǔ)為核心的技術(shù)內(nèi)容，也整理收集優(yōu)秀的學(xué)習(xí)資料厕氨。
后續(xù)還會(huì)翻譯大量資料到我們公眾號(hào)进每，有感興趣的朋友，可以加入我們命斧。
