最长间断序列

题目形容：给定一个未排序的整数数组 nums ，找出数字间断的最长序列（不要求序列元素在原数组中间断）的长度。

请你设计并实现工夫复杂度为 O(n) 的算法解决此问题。

示例阐明请见LeetCode官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：哈希表

因为哈希查找比拟快，所以用哈希表来辅助计算，具体处理过程如下：

  • 首先，用HashSet将原数组中的数字去重失去numsSet；
  • 而后，遍历numsSet中的所有数字，用currentConsecutiveNums记录以以后数字为终点，间断的数且在numsSet中的最长序列长度，通过哈希查找在numsSet中查找这些间断的数字，最初失去以后数字对应的最长间断序列长度；
  • 如果以后数字对应的最长间断序列长度比已知的最长间断序列longestConsecutiveNums大，则更新最长间断序列longestConsecutiveNums的值。

最初，返回longestConsecutiveNums即为间断的最长序列的长度。

import java.util.HashSet;import java.util.Set;public class LeetCode_128 {    /**     * 哈希表     *     * @param nums     * @return     */    public static int longestConsecutive(int[] nums) {        // 去重后的数        Set<Integer> numsSet = new HashSet<>();        for (int num : nums) {            numsSet.add(num);        }        // 记录最长的间断序列        int longestConsecutiveNums = 0;        for (Integer num : numsSet) {            if (!numsSet.contains(num - 1)) {                // 以后的数                int currentNum = num;                // 以后的数间断的序列的长度，初始值为1                int currentConsecutiveNums = 1;                // 获取以以后数字为终点，间断的数且在numsSet中的长度                while (numsSet.contains(currentNum + 1)) {                    currentNum += 1;                    currentConsecutiveNums += 1;                }                // 如果以后的最大间断长度大于最大的的间断序列，则更新最大的间断序列                longestConsecutiveNums = Math.max(longestConsecutiveNums, currentConsecutiveNums);            }        }        return longestConsecutiveNums;    }    public static void main(String[] args) {        int[] nums = new int[]{100, 4, 200, 1, 3, 2};        // 测试用例，冀望输入： 4        System.out.println(longestConsecutive(nums));    }}
【每日寄语】 第一个青春是上帝给的；第二个的青春是靠本人致力的。