LeetCode OJ - Longest Consecutive Sequence (C++) (try 15 times)

為了練習尋找實習時會碰到的問題，我用別人推薦的 LeetCode online judge。
希望能直接寫程式，不用事先編譯就能直接AC。
這是下面是我寫的Longest Consecutive Sequence 的解法。

To practice future interview question, I use LeetCode online judge.
I am trying to type code directly on website without compile in other tool.
The following program is my Longest Consecutive Sequence solution.

編譯錯誤次數 Compile Error number: 1
嘗試次數 Try number: 15 (AC: 3) (WA: 7) (TLE: 1) (CE: 4)
是否事先在其他工具編譯 if compile first in other tool: No

使用的程式語言 using programming language: C++
以前是否看過 seen this problem before: No

點這裡看題目 Click here to see this Problem!

我嘗試了四種方法，第一二種失敗，三四種成功
1. 只用一個map記錄目前最長的連續sequence數目：中間等於左右兩邊相加再加一
   --> 錯誤，因為有可能此sequence的最左右兩邊記錄的數字不同

2. 找最大跟最小值，從最小跑到最大找最長連續sequence
   --> TLE，因為這樣就不是O(n), 是O(整數長度)
   TLE case: [2147483646,-2147483647,0,2,2147483644,-2147483645,2147483645]

3. 把數字存在map之中，因為在用iterator 拜訪 map的時候，中間的index會自動的排序，
此時只需要找連續出現的最長index即可！

4. 使用兩個unordered_map記錄lower bound, upper bound，每次讀到新數字的時先預設大小的bound都是自己，再看看左右兩邊是不是已經有sequence，如果有的話就記錄左邊的lower bound跟右邊的 upper bound，最後只要把upper bound and lower bound的大小bound都更新為新的即可！！！！

下面分別是兩種解法～


If you want to use (copy, paste or quote) my original article, please contact me through email. (autek.roy@gmail.com) If there is any mistake or comment, please let me know. :D

如要使用(複製貼上或轉載)作者原創文章， 請來信跟我聯絡。(autek.roy@gmail.com) 如果有發現任何的錯誤與建議請留言或跟我連絡。 : )