之前寫過一篇這個(gè)題的，但是可能代碼比較復(fù)雜，這回來個(gè)簡(jiǎn)潔版的，這個(gè)是遞歸版本

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

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

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

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