LeetCode——Hot 100【最长连续序列 移动零】_top 100算法题地址

题目链接（一）

题目链接：https://leetcode.cn/problems/move-zeroes?envType=study-plan-v2&envId=top-100-liked

题目分析

问题：给定一个未排序的整数数组，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度，要求算法时间复杂度为 O (n)。

示例：

输入 : [100,4,200,1,3,2]，输出: 4 （对应序列 1,2,3,4）

输入 : [0,3,7,2,5,8,4,6,0,1]，输出: 9 （对应序列 0,1,2,3,4,5,6,7,8)

需要注意细节：

数组未排序，直接排序会导致 O (n log n) 时间复杂度，不符合要求。

需要高效判断数字的连续性。

需避免重复计算同一序列。

解题思路

利用哈希表（unordered_set ）存储数组元素，实现 O (1) 时间复杂度的元素查找，通过判断每个数字是否为序列起点，避免重复计算 （后面有详细解释）。

步骤：
去重处理：将数组元素存入 unordered_set ，会自动去除重复值（重复元素不影响连续序列长度）。

寻找序列起点：对于每个元素num，如果num-1不存在于 Set 中，则num是一个连续序列的起点。

计算序列长度：从起点开始，依次判断num+1、num+2… 是否存在unordered_set ，统计连续序列长度。

更新最大长度：记录所有序列中的最大长度。

如何避免重复计算？

通过判断num-1是否存在，确保每个连续序列只从起点开始计算一次。例如序列 1,2,3,4 ：只在num=1时进入计算（因为0不存在）num=2,3,4时因num-1存在，直接跳过，避免重复计算。

AC代码

class Solution {public: int longestConsecutive(vector<int>& nums) { unordered_set<int> st(nums.begin(),nums.end()); int length=0;//记录最终长度 for(auto ss:st) { if(!st.count(ss-1)) { int current=ss;//以该值为起点的序列 int curlength=1;//记录当前序列长度 while(st.count(++current)) {  curlength++; } length=max(length,curlength);//实时更新最终长度 } } return length; }};

补充

为什么用 unordered_set而不是 Set？
在 C++ 中，set和unordered_set均可实现去重和查找
set插入和查找为 O (log n)，总时间 O (n log n)。
unordered_set（哈希表实现，插入和查找 O (1)）。
当然这题体现不出来unorfered_set的价值。只是帮大家回顾一下它们各自复杂度。

题目链接（二）

题目链接：https://leetcode.cn/problems/move-zeroes?envType=study-plan-v2&envId=top-100-liked

题目分析​

问题：给定一个整数数组 nums，需要将所有的 0 移动到数组的末尾，同时保持非零元素的相对顺序不变，并且必须在不复制数组的情况下原地操作。​

示例：​
输入 [0,1,0,3,12]，输出 [1,3,12,0,0]​
输入 [0]，输出 [0]

注意点：

必须原地操作，不能借助额外的数组来存储元素​。
要保持非零元素的相对顺序不变。

解题思路

采用双指针法，通过两个指针 left 和 right 来遍历数组，实现零元素和非零元素的位置交换，从而将所有零元素移动到数组末尾。

left 指针：始终指向当前第一个零元素的位置，等待被非零元素替换​
right 指针：负责在 left 指针后面寻找非零元素，为替换做准备

具体操作步骤：

初始化两个指针 left 和 right，left 用于指向当前需要替换的零元素位置，right 用于寻找非零元素​。

当 right 指针遍历数组时，遇到非零元素且 left 指针指向零元素时，交换两个指针所指的元素​。

若 left 指针指向零元素且 right 指针也指向零元素，则只需移动 right 指针继续寻找非零元素​即可。

其他情况下，同时移动两个指针，继续遍历数组。

重复上述操作直到right指向数组的最后一个元素的下一个位置，此时我们就完成了将零元素全部移动到数组末尾的要求。

AC代码

class Solution {public: void moveZeroes(vector<int>& nums) { int n=nums.size(); int left=0; int right=left+1; while(right<n) { if((nums[right]!=0)&&(nums[left]==0)) { swap(nums[left],nums[right]); } if((nums[left]==0)&&(nums[right]==0)) {  right++;  continue; }  right++;  left++; } }};