LeetCode128.最长连续序列

 我这个方法有点投机取巧了，题目说时间复杂度最多O(n),而我调用了Arrays.sort(）方法，他的时间复杂度是n*log(n)，但是AC了，这样的话这道题还是非常简单的，创建一个Hashmap，以nums数组的元素作为key，以这个元素是连续序列中的第几个作为value，先把数组排一下序，然后从第一个开始往后遍历，如果map中有nums[i]这个key，可以直接跳过看下一个元素，如果没有这个key那就看有没有nums[i]-1这个key，也就是看nums[i]前面这个数有没有在数组中，如果有拿到这个nums[i]-1这个key的value，说明nums[i]-1在序列中的第value个，那么nums[i]就在序列中的第value+1个，map.put(nums[i],value+1)，同时维护一个ans，表示数组中最大的序列，看看value+1是不是比ans大，如果是则更新ans。如果map中没有nums[i]-1这个key，说明nums[i]前面的序列已经断掉了，以num[i]为起点重新建一个序列，那么num[i]就是序列中的第1个，所以map.put(nums[i],1)，以下是我的代码：

class Solution {public int longestConsecutive(int[] nums) {if(nums.length == 0)return 0;HashMap<Integer,Integer> map = new HashMap<>();int ans =1;Arrays.sort(nums);for(int i=0;i<nums.length;i++){if(map.containsKey(nums[i])){continue;}else{if(map.containsKey(nums[i]-1)){int value = map.get(nums[i-1])+1;map.put(nums[i],value);if(value > ans)ans=value;}else{map.put(nums[i],1);}} }return ans;}
}

看了一下题解，题解用的是Hashset。

class Solution {public int longestConsecutive(int[] nums) {Set<Integer> num_set = new HashSet<Integer>();for (int num : nums) {num_set.add(num);}int longestStreak = 0;for (int num : num_set) {if (!num_set.contains(num - 1)) {int currentNum = num;int currentStreak = 1;while (num_set.contains(currentNum + 1)) {currentNum += 1;currentStreak += 1;}longestStreak = Math.max(longestStreak, currentStreak);}}return longestStreak;}
}

他先把数组中的所有数全放进set里面，然后遍历set中的num，看看set中有没有num的前1个数num-1，如果没有，说明num就是一个序列的起点，把这个序列的长度先初始为1，然后用一个while循环去看看有没有num的下一个数，如果有的话，序列长度+1，num变为他的下一个数，没有的话循环结束，每次循环都更新longestStreak，最后返回longestStreak即可。

说实话我看完也有点疑惑，外层这个循环已经是O(n)了，里面还有一个while循环，这不是超了吗？好像是for里面只有几个序列的起点会进去，然后while里面也只有起点后面的几个数会进去，然后时间复杂度是O(2n)也就是O(n)。