赞
踩
思路(hashset):
将所有数字放入hashset,遍历hashset中的元素
向后枚举相邻的数字(即不断加一),判断后面一个数字是否在哈希表中
由于要求时间复杂度为O(n),因此要对上述过程进行优化
:
为了避免重复枚举序列,因此只对序列的起始数字向后枚举,因此需要判断一下当前数是否是序列的起始数
如何判断当前数x是不是某一个序列的起点呢?
只需要判断x-1是否存在即可,若x-1存在,那么说明这个数前面还有连续的数,即这个数不是起点。
---------------------------------------------------解法---------------------------------------------------:
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; } }
可能存在的问题:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。