当前位置:   article > 正文

[LeetCode]128. 最长连续序列(java实现)hashset

[LeetCode]128. 最长连续序列(java实现)hashset

1. 题目

在这里插入图片描述
在这里插入图片描述

2. 读题(需要重点注意的东西)

思路(hashset):

  1. 将所有数字放入hashset,遍历hashset中的元素

  2. 向后枚举相邻的数字(即不断加一),判断后面一个数字是否在哈希表

由于要求时间复杂度为O(n),因此要对上述过程进行优化

为了避免重复枚举序列,因此只对序列的起始数字向后枚举,因此需要判断一下当前数是否是序列的起始数

如何判断当前数x是不是某一个序列的起点呢?
只需要判断x-1是否存在即可,若x-1存在,那么说明这个数前面还有连续的数,即这个数不是起点。

3. 解法

---------------------------------------------------解法---------------------------------------------------

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> hashset = new HashSet<>();
        for(int num : nums) hashset.add(num);
        int res = 0;
        for(int i = 0;i < nums.length;i++){
            int x = nums[i];
            if(!hashset.contains(x-1)){
                int y = x;
                while(hashset.contains(y+1)) y++;
                res = Math.max(res,y - x + 1);
            }
        }
        return res;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

可能存在的问题:

4. 可能有帮助的前置习题

5. 所用到的数据结构与算法思想

6. 总结

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/不正经/article/detail/235840
推荐阅读
相关标签
  

闽ICP备14008679号