LeetCode 热题 100（每日两题）-Day2

坚持打卡第二天昨天的哈希表大显神威今天我们将继续探索哈希集合的妙用并引入数组操作中极其重要的技巧——双指针快慢指针。一、最长连续序列LeetCode 第 128 题难度中等。这道题的难点在于题目强制要求时间复杂度必须为 O(n)题目描述给定一个未排序的整数数组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解题思路为了实现 O(n) 的时间复杂度我们需要空间换时间利用HashSet提供 O(1) 的查找能力。去重与建立哈希集合首先遍历一次数组将所有元素放入HashSet中不仅去重还方便后续快速查找某个数字是否存在。寻找序列起点遍历HashSet中的数字为了避免重复计算同一个序列我们只从序列的起点开始计算。如果集合中不存在num - 1说明当前的num就是一个连续序列的起点。向后延伸寻找确定了起点后通过一个while循环不断查找currentNum 1是否在集合中如果在则当前序列长度加一并继续往后找。更新最大长度每次找到一个完整序列后将它的长度与历史最大长度maxLength进行比较并更新。代码实现javaimport java.util.HashSet; import java.util.Set; class Solution { public static int longestConsecutive(int[] nums) { if (nums null || nums.length 0) { return 0; } SetInteger set new HashSet(); for (int num : nums) { set.add(num); } int maxLength 0; for (int num : set) { if (!set.contains(num - 1)) { int currentNum num; int currentLength 1; while (set.contains(currentNum 1)) { currentNum; currentLength; } maxLength Math.max(maxLength, currentLength); } } return maxLength; } }二、移动零LeetCode 第 283 题难度简单。这是一道非常经典的“原地修改数组”问题非常适合用来练手双指针思想。题目描述给定一个数组nums编写一个函数将所有0移动到数组的末尾同时保持非零元素的相对顺序。请注意必须在不复制数组的情况下原地对数组进行操作。示例 1:输入:nums [0,1,0,3,12]输出:[1,3,12,0,0]示例 2:输入:nums [0]输出:[0] 解题思路既然要求在原地操作且不打乱非零元素的相对顺序我们可以使用快慢指针的技巧定义两个指针slow慢指针用于指向下一个非零元素应当放置的位置fast快指针用于遍历整个数组。初始时slow和fast都指向索引 0。fast指针开始向后遍历数组如果nums[fast]不是0我们就将它和nums[slow]所在位置的元素进行交换。交换后slow指针向后移动一步slow。如果nums[fast]是0则跳过fast继续向前走。这样遍历一遍结束后所有的非零元素都被按原本的顺序“挤”到了数组的前面而所有的 0 都被交换到了数组的末尾。代码实现 (Java)class Solution { public static void moveZeroes(int[] nums) { int slow 0; for (int fast 0; fast nums.length; fast) { if (nums[fast] ! 0) { int temp nums[slow]; nums[slow] nums[fast]; nums[fast] temp; slow; } } } }学习总结 今天的两道题让我们看到了巧妙利用数据结构HashSet和算法技巧双指针带来的性能提升。“最长连续序列”的起点判定剪枝思想非常精妙而“移动零”则是双指针在数组原地操作中的典型应用值得反复回味