LeetCode hot 100 每日一题(3)--128. 最长连续序列
今天是每日一题的第三题，依然是哈希表系列。
让我们看看题目描述：
给定一个未排序的整数数组
nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为O(n)的算法解决此问题。示例 1：
输入： nums = [100,4,200,1,3,2]
输出： 4
解释： 最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2：
输入： nums = [0,3,7,2,5,8,4,6,0,1]
输出： 9示例 3：
输入： nums = [1,0,1,2]
输出： 3提示：
- 0 <= nums.length <= 1 0 5 10^5 105
- − 1 0 9 -10^9 −109 <= nums[i] <= 1 0 9 10^9 109
同样的，有一点看不懂这道题目，下面进入说人话环节：
给你一个乱序数组，需要找出其中连续数字的最长序列，返回这个序列的长度。
如果问连续数字是什么？请你现在就开始从1开始数数，这就是连续数字，1234就是一个连续数字序列。
解法1
class Solution {
public int longestConsecutive(int[] nums) {
// 将数组中的每个数字加入HashSet中，方便后续快速查找
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
num_set.add(num);
}
// 初始化变量，用于记录最长连续序列的长度
int longestStreak = 0;
// 遍历HashSet中的每个数字
for (int num : num_set) {
// 如果当前数字的前一个数字不存在，说明这个数字可能是一个连续序列的起点
if (!num_set.contains(num - 1)) {
// 以当前数字作为连续序列的起点
int currentNum = num;
// 初始化当前连续序列的长度至少为1
int currentStreak = 1;
// 检查连续序列中是否存在下一个数字
while (num_set.contains(currentNum + 1)) {
// 找到下一个数字，将当前数字更新为下一个数字
currentNum += 1;
// 当前连续序列长度增加1
currentStreak += 1;
}
// 更新全局最长连续序列长度
longestStreak = Math.max(longestStreak, currentStreak);
}
}
// 返回找到的最长连续序列的长度
return longestStreak;
}
}
这里是总体思路：
- 首先将数组中所有数字存入集合中，利用集合自动去重。
- 对于每个数字，通过判断它的前一个数字是否存在来确定是否为连续序列的起点（只有序列起点才需要计算序列长度）。
- 如果是序列起点，就通过 while 循环不断查找后续连续的数字，直到无法找到连续的数字为止，从而计算出当前序列的长度。
- 最后比较所有连续序列的长度，返回最长的那个。
问题与解答
[NOTE] 问题1
1.为什么要使用HashSet这种数据类型，而不是HashMap？
- 解释
在这道题中，我们只关心数字是否存在，而不需要为每个数字关联额外的数据（value）。HashSet是专门用来存储不重复元素的集合，并且它的内部实现就是基于HashMap，但只使用了 key，而忽略了 value。使用 HashSet 可以让代码更加简洁，并且更符合题目的需求。
- 数据需求不同：
HashSet 只存储单个元素（key），而 HashMap 需要存储键值对（key-value）。
对于仅需要判断某个数字是否存在的场景，HashSet 更直观、语义更明确。- 简洁性和易用性：
HashSet的接口更简单，不需要处理不必要的 value 部分。使用HashSet代码更容易理解和维护。- 性能和内存：
虽然两者底层实现类似，但HashSet只保存 key，可能在内存和操作上有更小的开销。
因此，在这道题中选择 HashSet 是因为它正好满足只需要存储不重复数字、快速判断数字存在性的需求。
[NOTE] 问题2
2.while循环找不到下一个数字才会退出吗？
- 解释
是的，while 循环的条件是 num_set.contains(currentNum + 1)，只要集合中存在下一个数字（即 currentNum + 1），就会一直执行循环。当条件不满足，即找不到连续的下一个数字时，循环才会退出。
实例
下面通过一个例子来了解整体流程，加深印象。
输入：nums = [100,4,200,1,3,4,2]
输出：4
+--------------------------+
| 输入数组 |
| [100, 4, 200, 1, 3, 4, 2] |
+-------------+-------------+
│
▼
+---------------------------+
| 转换为 HashSet |
| {1, 2, 3, 4, 100, 200} |
+-------------+-------------+
│
▼
+--------------------------+
| 遍历 HashSet 中的每个数字 |
+-------------+------------+
│
┌─────────────────┴─────────────────┐
│ │
▼ ▼
+----------------------+ +----------------------+
| 数字 1 | | 数字 2 |
| 判断: 1-1 = 0不存在 | | 判断: 2-1 = 1存在 |
| → 是序列起点 | | → 不是起点，跳过 |
+----------+-----------+ +----------------------+
│
▼
+--------------------------+
| 从1开始扩展连续序列: |
| 1 → 2 （存在） |
| 2 → 3 （存在） |
| 3 → 4 （存在） |
| 4 → 5 （不存在） |
| 序列：[1, 2, 3, 4] |
| 长度 = 4 |
+----------+-------------+
│
▼
+--------------------------+
| 更新最长序列长度为 4 |
+--------------------------+
│
▼
┌───────────────────┴──────────────┐
▼ ▼
+------------------+ +------------------+
| 数字 100 | | 数字 200 |
| 判断: 100-1=99不存在 | | 判断: 200-1=199不存在|
| → 是序列起点 | | → 是序列起点 |
| 扩展: 100 → 101不存在| | 扩展: 200 → 201不存在|
| 序列长度 = 1 | | 序列长度 = 1 |
+------------------+ +------------------+
│ │
└───────────┬───────────┘
▼
+---------------------------+
| 最终最长序列长度 = 4 |
+----------------------------+
总结回顾
下面是HashSet在 Java 中的声明和基本用法示例，以及详细解释：
在 Java 中，HashSet 是一个基于哈希表（HashMap）实现的集合类，用于存储不重复的元素。它不保证元素的顺序，即元素的插入顺序可能与迭代顺序不同。
声明 HashSet：
要使用 HashSet，首先需要导入 java.util.HashSet 类。然后，可以通过以下方式声明一个 HashSet：
import java.util.HashSet;
import java.util.Set;
// 创建一个存储字符串的 HashSet
Set<String> set = new HashSet<>();
HashSet 的常用方法：
-
添加元素：
使用add(E e)方法将元素添加到集合中。如果元素已存在，添加操作不会生效，且返回 false。set.add("Apple"); set.add("Banana"); set.add("Apple"); // 重复元素，不会被添加 -
删除元素：
使用remove(Object o)方法从集合中移除指定的元素。如果元素存在且被移除，返回 true；否则，返回 falseset.remove("Banana"); -
检查元素是否存在：
使用 contains(Object o) 方法判断集合中是否包含指定的元素。boolean exists = set.contains("Apple"); -
获取集合大小：
使用size()方法获取集合中元素的数量。int size = set.size(); -
清空集合：
使用clear()方法移除集合中的所有元素。set.clear(); -
判断集合是否为空：
使用isEmpty()方法检查集合是否为空。boolean isEmpty = set.isEmpty(); -
遍历集合：
可以使用增强型 for 循环或迭代器来遍历 HashSet 中的元素。// 使用增强型 for 循环 for (String item : set) { System.out.println(item); } // 使用迭代器 Iterator<String> iterator = set.iterator(); while (iterator.hasNext()) { System.out.println(iterator.next()); }
以下是一个完整的示例，演示了 HashSet 的声明和常用方法的使用：
import java.util.HashSet;
import java.util.Set;
import java.util.Iterator;
public class HashSetExample {
public static void main(String[] args) {
// 创建一个 HashSet
Set<String> set = new HashSet<>();
// 添加元素
set.add("Apple");
set.add("Banana");
set.add("Cherry");
set.add("Apple"); // 重复元素，不会被添加
// 显示集合中的元素
System.out.println("HashSet: " + set);
// 检查元素是否存在
boolean containsApple = set.contains("Apple");
System.out.println("Contains 'Apple': " + containsApple);
// 删除元素
set.remove("Banana");
System.out.println("After removing 'Banana': " + set);
// 获取集合大小
int size = set.size();
System.out.println("Size of HashSet: " + size);
// 遍历集合
System.out.println("Iterating over HashSet:");
for (String item : set) {
System.out.println(item);
}
// 清空集合
set.clear();
System.out.println("After clearing, is HashSet empty? " + set.isEmpty());
}
}
输出：
HashSet: [Apple, Banana, Cherry]
Contains 'Apple': true
After removing 'Banana': [Apple, Cherry]
Size of HashSet: 2
Iterating over HashSet:
Apple
Cherry
After clearing, is HashSet empty? true
需要注意的是，HashSet 不保证元素的迭代顺序，因此输出的顺序可能与插入顺序不同。