?我這個方法有點投機取巧了，題目說時間復雜度最多O(n),而我調用了Arrays.sort(）方法，他的時間復雜度是n*log(n)，但是AC了，這樣的話這道題還是非常簡單的，創(chuàng)建一個Hashmap，以nums數組的元素作為key，以這個元素是連續(xù)序列中的第幾個作為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循環(huán)去看看有沒有num的下一個數，如果有的話，序列長度+1，num變?yōu)樗南乱粋€數，沒有的話循環(huán)結束，每次循環(huán)都更新longestStreak，最后返回longestStreak即可。

說實話我看完也有點疑惑，外層這個循環(huán)已經是O(n)了，里面還有一個while循環(huán)，這不是超了嗎？好像是for里面只有幾個序列的起點會進去，然后while里面也只有起點后面的幾個數會進去，然后時間復雜度是O(2n)也就是O(n)。文章來源地址http://www.zghlxwxcb.cn/news/detail-659844.html

到了這里，關于LeetCode128.最長連續(xù)序列的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！