難度：中等
頻次：42
題目：給定一個未排序的整數數組 nums ，找出數字連續的最長序列（不要求序列元素在原數組中連續）的長度。

請你設計并實現時間復雜度為 O(n) 的算法解決此問題。

解題思路：因為要O(n)，不能重新排序，hashmap+動態規劃
可以hashmap+set（去重+判斷當都一個key是否存在）
注意：

• 創建一個hashma放nums中的元素
• 如果num之前沒有放到hashmap中
  - 讀取num-1 num+1值的連續序列值，分別作為left和right
  - 計算加上num的連續序列值 len=left+right+1
  - 跟之前的結果做對比，看看哪個len比較大
  - 把num的key放回hashmap中
  - 把num-left,num+right的 值標記為len

代碼：

class Solution {public int longestConsecutive(int[] nums) {Map<Integer,Integer> map=new HashMap<>();//res存儲結果int res=0;//for循環遍歷for(int num:nums){//map中不存在numif(!map.containsKey(num)){//讀取num左邊、右邊的連續序列值int left=map.getOrDefault(num-1,0);int right=map.getOrDefault(num+1,0);//算num的連續序列值int len=left+right+1;//跟之前遍歷過的數字比較，看看比較長的連續序列值是多少res=Math.max(len,res);//把計算的結果放回map中//num的值可以為任意值map.put(num,-1);//num左邊連續序列值（left）的key都標記為lenmap.put(num-left,len);//右邊同理map.put(right+num,len);}}return res;} }

總結

以上是生活随笔為你收集整理的多看看 leetcode 128. 最长连续序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。