Hot100 Hash系列第3题

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

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

思路：如果使用快排，复杂度为O(nlogn)不符合要求，想要符合该复杂度，可以使用Hash表查询为O(1)的特点，将数组插入HashSet中，然后进行复杂度为O(n)的记录最长数组。

代码1：

import java.util.HashSet;
import java.util.Set;
public class LongestConsecutive {
public class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
 
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
 
        int maxLength = 0;
 
        for (int num : numSet) {
            // 只有当num-1不存在时，才认为num是新序列的起点
            if (!numSet.contains(num - 1)) {
                int currentNum = num;//感觉这个变量不需要
                int currentLength = 1;
 
                // 向序列右侧扩展
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }
 
                // 更新最长序列长度
                maxLength = Math.max(maxLength, currentLength);
            }
        }
 
        return maxLength;
    }
}
public static void main(String[] args) {
        LongestConsecutive solution = new LongestConsecutive();
        int[] nums = {100, 4, 200, 1, 3, 2};
        System.out.println(solution.longestConsecutive(nums)); // 输出4，对应序列1,2,3,4
    }
    
}

代码2：(这个速度比代码一还慢一点点)

class Solution {
    public int longestConsecutive(int[] nums) {
        int res = 0;    // 记录最长连续序列的长度
        Set<Integer> numSet = new HashSet<>();  // 记录所有的数值
        for(int num: nums){
            numSet.add(num);    // 将数组中的值加入哈希表中
        }
        int seqLen;     // 连续序列的长度
        for(int num: numSet){
            // 如果当前的数是一个连续序列的起点，统计这个连续序列的长度
            if(!numSet.contains(num - 1)){
                seqLen = 1;
                while(numSet.contains(++num))seqLen++;  // 不断查找连续序列，直到num的下一个数不存在于数组中
                res = Math.max(res, seqLen);    // 更新最长连续序列长度
            }
        }
        return res;
    }
}

这段代码的时间复杂度是O(n)，其中n是输入列表nums的长度。下面是详细的解释：

1. num_set = set(nums): 这步操作将列表转换为集合，对于包含n个元素的列表，转换为集合的时间复杂度是O(n)，因为集合不允许重复元素，所以需要遍历列表中的每个元素来创建集合。
2. 接下来的for循环遍历了集合num_set中的每个元素一次。由于集合中的元素数量最多与列表nums相同（在没有重复元素的情况下），所以这个循环的时间复杂度是O(n)。
3. 在for循环内部，有一个while循环，它用于找出以当前数字为起点的最长连续序列。在最坏的情况下，这个while循环可能需要执行n次，因为如果数组是连续的，那么每次循环都需要检查到数组的末尾。然而，由于集合查找操作的时间复杂度是O(1)，这个while循环并不会显著增加总体的时间复杂度。

综上所述，虽然内部有一个while循环，但由于集合的查找操作是O(1)的，整个算法的主导时间复杂度仍然是O(n)。这是因为主要的时间消耗在于遍历集合中的元素，而集合中的元素数量不会超过输入列表的长度。因此，整个函数的时间复杂度是O(n)。

根据佬的题解做的一点笔记。

1. 遍历数组，放到 set 中

a. set 有去重的作用，对于此题的求连续序列很适合

b. set.contains(i) 的查找某个元素是否存在的时间复杂度是 O(1)

c. 补充知识：

ⅰ. 调用 HashSet 的 contains(Object o) 方法时，会实际上是调用底层 HashMap 的 containsKey(Object key) 方法来判断是否包含指定的元素。由于哈希表的查找操作是平均情况下是 O(1) 的时间复杂度，因此 HashSet 的查找元素的时间复杂度也是 O(1)。

ⅱ. HashMap底层采用数组+链表+红黑树的数据结构实现。 数组是HashMap的主体，用于存储键值对；链表用于解决哈希冲突；红黑树是在链表长度超过一定阈值（默认为8）时，将链表转换为红黑树，以提高查找效率

2. 遍历 set，考虑当前元素 cur ，如果 cur+1 在 set 中，就 sublength++

a. 细节：处理当前元素 cur 时，如果 set 中存在 cur-1，其实不用处理 cur 了，因为 cur 是 cur-1 的下一个，会存在以 cur-1 打头的连续序列中参与计数。