Given an unsorted array of integers
You must write an algorithm that runs in
Example 1:
Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is[1, 2, 3, 4] . Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9
Constraints:
0 <= nums.length <= 105 -109 <= nums[i] <= 109
題目是要找到在一個 array 中,連續數字的最長長度
一開始想用sliding window,但題目的 array 不是 sorted 的,看起來不可行
題目又要求 O(n) 的時間複雜度
能加速歷遍速度的,看起來要用到 hash map or hash set
這邊選擇使用 hash set,可以直接把重複數字的變因消除掉
然後因為從 4 往下找到 1,也就是 4 -> 3 -> 2 -> 1
和從 1 找到 4,也就是 1 -> 2 -> 3 -> 4,兩者是一樣的
所以一旦有找過,就可以移除掉
因此,每個數字,我們就往上和往下找,一旦在 set 裡面,移除並移動指標
過程中也記錄最大值
Kotlin
沒有留言:
張貼留言