之前寫過一篇這個題的，但是可能代碼比較復雜，這回來個簡潔版的，這個是遞歸版本

可以看看之前的版本，兩個版本面試用哪個都保過

解法都在代碼里，不懂就留言或者私信

class Solution {/**對于之前的解法，我現(xiàn)在提供一共更優(yōu)的解，但是這種可能會比較難懂一些（思想方面）代碼其實是很簡潔的，總體思想如下：不需要排序直接把所有數(shù)放入map，map的key是當前數(shù)字，value是當前數(shù)開始的連續(xù)的長度初始值都是1，后面再遍歷數(shù)組，遍歷過程中查找當前數(shù)+1在map中的記錄，直到找不到為止，比如我們第一個示例[100,4,200,1,3,2]我們便利到1的時候會在map中找到2的記錄，然后取它的value+1，找2的過程又會遞歸查找3,直到找不到5的時候停，5的value是0,4取0+1=13取1+1=2 2取2+1=3,1取3+1=4而對于100，我們查找101就直接失敗了，所以以它連續(xù)的就是0+1=1*/public int longestConsecutive(int[] nums) {/**如果長度小于2，有多少數(shù)就有多大的連續(xù)長度*/if(nums.length < 2) {return nums.length;}/**大于等于2的情況我們先把每個數(shù)都放在map里，key是數(shù)字本身，value是以它為開始的連續(xù)長度，初始值都設置為1這樣做還有另外一個原因就是可以避免重復項的干擾*/Map<Integer, Integer> countMap = new HashMap<>();for(int num : nums) {countMap.put(num, 1);}/**定義結(jié)果值,既然有數(shù)，至少也得是個1吧*/int longest = 1;/**遍歷數(shù)組，計算以當前數(shù)字開始的最長的長度*/for(int num : nums) {int curAns = countConsecutive(countMap, num);longest = Math.max(longest, curAns);}return longest;}/**通過countMap查找target開始的連續(xù)數(shù)字的長度 */public int countConsecutive(Map<Integer, Integer> countMap, int target) {/**我們通過主方法調(diào)用這個方法的時候當然target肯定是存在的，但是我們會遞歸調(diào)用 target+1直到不存在為止，所以這里一定要判斷是不是存在，不存在返回0 */if(!countMap.containsKey(target)) {return 0;}/**這里有個大的優(yōu)化，一定要做，如果當前map中存的target對應的value已經(jīng)大于1了，說明算過了，不用重復計算不然每次都得從頭開始一個一個算，肯定會超時的，比如先找1，然后找2.。。一直找到10000肯定不行，如果之前已經(jīng)有2的記錄了（大于1）現(xiàn)在取2的記錄+1就行了 */if(countMap.get(target) > 1) {return countMap.get(target);}/**如果存在，找target+1開頭的最大長度 */int count = countConsecutive(countMap, target + 1) + 1;/**不要忘了記錄當前的結(jié)果*/countMap.put(target, count);return count;}
}

運行時間和百分百確實有所提升，但是真的是同樣的時間復雜度，也沒感覺常數(shù)時間降低了多少