LeetCode 哈希表专题

2020/01/22 Prolems

目录

128. 最长连续序列 困难

  • 题目描述

    给定一个未排序的整数数组,找出最长连续序列的长度。

    要求算法的时间复杂度为 O(n)。

    Example:

    输入: [100, 4, 200, 1, 3, 2]
    输出: 4
    解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

  • 解法

    用一个 map 存储出现过的值。之后找出现前和出现后的连续值,记录出现过,这样当在遍历到它就可以直接跳过。

  • 代码

      class Solution {
          public int longestConsecutive(int[] nums) {
              Map<Integer,Integer> map = new HashMap<>(); // 1 代表有,NULL 就是没有,2 就是已经算过了
                
              for(int i=0;i<nums.length;i++){
                  map.put(nums[i],1);
              }
              int res = 0;
              for(int i=0;i<nums.length;i++){
                  Integer temp = map.get(nums[i]);
                  if(temp==2) continue;
                  int count = 0;
                  int minus = nums[i]-1;
                  while(map.get(minus)!=null){
                      count++;
                      map.put(minus,2);
                      minus--;
                  }
                  int add = nums[i]+1;
                  while(map.get(add)!=null){
                      count++;
                      map.put(add,2);
                      add++;
                  }
                  res = Math.max(res,count+1); //还有它本身
              }
              return res;
          }
      }
    

Search

    Table of Contents