第三天-128.最长连续序列

这道题我完全没有思路，求助gpt，让它给我思路：

这个问题要求找出数组中数字连续的最长序列，并且时间复杂度必须是 O(n)，可以采用哈希集（HashSet）来帮助我们高效地判断数字是否存在。以下是解决问题的思路：

我前面两天做的都是hashmap，这道题我也是想着hashmap解决，但是解不出来，还是基础知识太薄弱了，精细刷题，不求多，但求刷的每道题都会！

思路：

1. 使用哈希表进行快速查找：
- 由于我们需要在 O(1) 的时间内判断某个数字是否存在，可以利用哈希集（`HashSet`）来存储数组中的所有数字。

2. 找序列的起点：
- 遍历数组中的每个数字 `num`，如果 `num-1` 不在哈希集中，那么这个数字 `num` 可能是一个序列的起点。因为只有可能是序列的第一个数字，我们才会从这里开始向后查找。
- 例如，假设有一组数字 `100, 4, 200, 1, 3, 2`，当遍历到 `1` 时，如果 `0` 不在哈希集中，说明 `1` 是序列 `1, 2, 3, 4` 的起点。

3. 计算序列的长度：
- 一旦确定了序列的起点（即 `num-1` 不存在），我们就可以从这个数字开始，不断检查 `num+1`, `num+2`, ... 是否存在于哈希集中，直到序列断开。记录下当前序列的长度。

4. 更新最大长度：
- 在每个序列计算完成之后，更新当前找到的最长序列长度。

5. 时间复杂度：
- 由于每个数字最多会被处理一次（因为只从序列的起点开始扩展），所以时间复杂度是 O(n)。

算法步骤：

1. 将数组中的所有元素放入哈希集。
2. 遍历数组中的每个元素，如果它的前一个数字（`num - 1`）不在哈希集中，说明它是一个序列的起点。
3. 以这个起点为起始，找出所有连续的数字，并计算序列的长度。
4. 更新最大序列长度。
5. 最终返回最长的序列长度。

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums.length==0||nums.length==1){
            return nums.length;
        }
        Set<Integer> set=new HashSet<>();
        for(int num:nums){
            set.add(num);
        }
        int longest=1;
        for(int num:set){
            if(!set.contains(num-1)){
                int current=1;
                int currentnum=num;
                while(set.contains(currentnum+1)){
                    current++;
                    currentnum++;
                }
                longest=Math.max(current,longest);
            }
        }
        return longest;
    }
}

代码解析：

1. HashSet：将所有元素添加到哈希集中，这样可以在 O(1) 的时间内查找元素是否存在。
2. 遍历数组：对于每个数字，如果 `num - 1` 不在哈希集中，说明它是一个序列的起点。
3. 找连续数字：从当前数字开始，检查是否有下一个连续的数字，直到找不到为止。记录序列的长度并更新最长序列。
4. 返回结果：最后返回最长的序列长度。

时间复杂度分析：
- 将所有元素加入哈希集的时间复杂度是 O(n)。
- 遍历每个数字并查找序列长度的时间复杂度也是 O(n)，因为每个数字最多只会被查找一次。
- 总的时间复杂度是 O(n)。

总结：

1.一开始并不明白时间复杂度为什么是o(n)。

2.我在while循环内部使用num++，虽然不影响外部的num（基本类型，传递值），但是这样做并不规范。

3.int longest=Math.max(current,longest);是错误的，因为在此之前已经声明过longest了。

4.longest=Math.max(current,longest);也可以用三目运算符