Leetcode面试经典150题-128.最长连续序列-递归版本另解

之前写过一篇这个题的，但是可能代码比较复杂，这回来个简洁版的，这个是递归版本

可以看看之前的版本，两个版本面试用哪个都保过

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

class Solution {/**对于之前的解法，我现在提供一共更优的解，但是这种可能会比较难懂一些（思想方面）代码其实是很简洁的，总体思想如下：不需要排序直接把所有数放入map，map的key是当前数字，value是当前数开始的连续的长度初始值都是1，后面再遍历数组，遍历过程中查找当前数+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就直接失败了，所以以它连续的就是0+1=1*/public int longestConsecutive(int[] nums) {/**如果长度小于2，有多少数就有多大的连续长度*/if(nums.length < 2) {return nums.length;}/**大于等于2的情况我们先把每个数都放在map里，key是数字本身，value是以它为开始的连续长度，初始值都设置为1这样做还有另外一个原因就是可以避免重复项的干扰*/Map<Integer, Integer> countMap = new HashMap<>();for(int num : nums) {countMap.put(num, 1);}/**定义结果值,既然有数，至少也得是个1吧*/int longest = 1;/**遍历数组，计算以当前数字开始的最长的长度*/for(int num : nums) {int curAns = countConsecutive(countMap, num);longest = Math.max(longest, curAns);}return longest;}/**通过countMap查找target开始的连续数字的长度 */public int countConsecutive(Map<Integer, Integer> countMap, int target) {/**我们通过主方法调用这个方法的时候当然target肯定是存在的，但是我们会递归调用 target+1直到不存在为止，所以这里一定要判断是不是存在，不存在返回0 */if(!countMap.containsKey(target)) {return 0;}/**这里有个大的优化，一定要做，如果当前map中存的target对应的value已经大于1了，说明算过了，不用重复计算不然每次都得从头开始一个一个算，肯定会超时的，比如先找1，然后找2.。。一直找到10000肯定不行，如果之前已经有2的记录了（大于1）现在取2的记录+1就行了 */if(countMap.get(target) > 1) {return countMap.get(target);}/**如果存在，找target+1开头的最大长度 */int count = countConsecutive(countMap, target + 1) + 1;/**不要忘了记录当前的结果*/countMap.put(target, count);return count;}
}

运行时间和百分百确实有所提升，但是真的是同样的时间复杂度，也没感觉常数时间降低了多少