Leetcode 134 存在重复元素 II | 最长连续序列

1 题目

219. 存在重复元素 II

给你一个整数数组nums和一个整数k，判断数组中是否存在两个不同的索引i和j，满足nums[i] == nums[j]且abs(i - j) <= k。如果存在，返回true；否则，返回false。

示例 1：

输入：nums = [1,2,3,1], k= 3输出：true

示例 2：

输入：nums = [1,0,1,1], k=1输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k=2输出：false

提示：

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

2 代码实现

思考

c++

class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_map <int,int > num_index ; for (int i = 0 ; i < nums.size() ; i++){ if (num_index.count(nums[i]) && i - num_index[nums[i]] <= k ){ return true ; } num_index[nums[i]] = i ; } return false ; } };

js

/** * @param {number[]} nums * @param {number} k * @return {boolean} */ var containsNearbyDuplicate = function(nums, k) { const numIndex = {} ; for (let i = 0 ; i < nums.length ; i ++){ const curSum = nums[i]; if (numIndex.hasOwnProperty(curSum) && i - numIndex[curSum] <= k ){ return true ; } numIndex[curSum] = i ; } return false ; };

这个题目之前都还做过，偷看了一下以前的提交记录，用的滑动窗口。如果要用哈希表，这应该怎么做呢？

题解

1. 题目分析

题目要求判断数组中是否存在两个不同索引的相同元素，且它们的索引差的绝对值不超过k。核心难点在于：

• 需要高效判断「重复元素」+「索引差限制」
• 数组长度可达 10⁵，暴力枚举（O (n²)）会超时，必须用 O (n) 或 O (n log n) 解法

2. 哈希表解法（最优）

思路

用哈希表（unordered_map）存储每个元素最后一次出现的索引：

1. 遍历数组，对每个元素nums[i]：
   • 如果哈希表中已存在该元素，且当前索引i与哈希表中存储的索引的差值 ≤k→ 直接返回true
   • 如果哈希表中已存在但差值 >k→ 更新哈希表中该元素的索引为当前i（保留最近的索引，后续更易满足 ≤k）
   • 如果不存在 → 将该元素和索引i存入哈希表
2. 遍历结束未找到符合条件的元素 → 返回false

代码实现

#include <iostream> #include <vector> #include <unordered_map> using namespace std; bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_map<int, int> num_index; // key: 数组元素, value: 元素最后出现的索引 for (int i = 0; i < nums.size(); ++i) { // 检查当前元素是否已存在，且索引差≤k if (num_index.count(nums[i]) && i - num_index[nums[i]] <= k) { return true; } // 更新为最新索引（无论是否存在，都要更新，保证后续判断用最近的索引） num_index[nums[i]] = i; } return false; } // 测试用例 int main() { // 示例1 vector<int> nums1 = {1,2,3,1}; int k1 = 3; cout << (containsNearbyDuplicate(nums1, k1) ? "true" : "false") << endl; // true // 示例2 vector<int> nums2 = {1,0,1,1}; int k2 = 1; cout << (containsNearbyDuplicate(nums2, k2) ? "true" : "false") << endl; // true // 示例3 vector<int> nums3 = {1,2,3,1,2,3}; int k3 = 2; cout << (containsNearbyDuplicate(nums3, k3) ? "true" : "false") << endl; // false return 0; }

代码解释

• 哈希表选择：unordered_map是哈希表实现，查询 / 插入的平均时间复杂度为 O (1)，整体时间复杂度 O (n)
• 核心逻辑：
  • num_index.count(nums[i])：判断当前元素是否在哈希表中（是否出现过）
  • i - num_index[nums[i]] <= k：判断索引差是否满足条件
  • 每次遍历都更新哈希表：即使元素已存在但索引差不满足，也要更新为当前索引（因为后续元素与当前索引的差值更小，更易满足 ≤k）
• 空间复杂度：O (n)（最坏情况数组无重复元素，哈希表存储所有元素）

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 <= 105
• -109 <= nums[i] <= 109

4 代码实现

c++

class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set <int> num_set; for (int num : nums ){ num_set.insert(num); } int max_len = 0 ; for (int num : num_set){ if (!num_set.count(num - 1)){ int cur_num = num ; int cur_len = 1 ; while (num_set.count(cur_num + 1)) { cur_num ++ ; cur_len ++ ; } max_len = max(max_len, cur_len); } } return max_len; } };

js

/** * @param {number[]} nums * @return {number} */ var longestConsecutive = function(nums) { const numSet = new Set(nums); let maxLen = 0 ; for (const num of numSet){ if (!numSet.has(num - 1 )){ let curNum = num ; let curLen = 1 ; while (numSet.has(curNum + 1 )){ curNum ++ ; curLen ++ ; } maxLen =Math.max(maxLen,curLen); } } return maxLen; };

思考

先存入哈希表，把哈希表内排序，然后再怎么判断最长连续的序列呢？

题解

1. 题目分析

题目要求找到未排序数组中数字连续的最长序列长度，且算法时间复杂度必须为 O (n)。

• 核心难点：不能用排序（排序时间复杂度至少 O (n log n)），必须通过哈希表实现 O (n) 效率。
• 关键思路：
  1. 用哈希集合存储所有数字（O (1) 查询），避免重复处理。
  2. 只从「连续序列的起点」（即num-1不在集合中）开始遍历，避免重复计算（比如 1、2、3、4 只从 1 开始算，2/3/4 直接跳过）。
  3. 对每个起点，逐步找num+1、num+2... 直到不存在，统计长度。

2. C++ 代码实现（O (n) 最优解）

#include <iostream> #include <vector> #include <unordered_set> using namespace std; class Solution { public: int longestConsecutive(vector<int>& nums) { // 步骤1：将数组存入哈希集合，去重 + O(1) 查询 unordered_set<int> num_set; for (int num : nums) { num_set.insert(num); } int max_len = 0; // 记录最长连续序列长度 // 步骤2：遍历每个数字，只处理「连续序列的起点」 for (int num : num_set) { // 关键：如果 num-1 不在集合中，说明 num 是连续序列的起点 if (!num_set.count(num - 1)) { int current_num = num; int current_len = 1; // 当前连续序列长度 // 步骤3：向后找连续数字（num+1, num+2...） while (num_set.count(current_num + 1)) { current_num += 1; current_len += 1; } // 更新最长长度 max_len = max(max_len, current_len); } } return max_len; } }; // 测试用例 int main() { Solution sol; // 示例1 vector<int> nums1 = {100,4,200,1,3,2}; cout << sol.longestConsecutive(nums1) << endl; // 4 // 示例2 vector<int> nums2 = {0,3,7,2,5,8,4,6,0,1}; cout << sol.longestConsecutive(nums2) << endl; // 9 // 示例3 vector<int> nums3 = {1,0,1,2}; cout << sol.longestConsecutive(nums3) << endl; // 3 return 0; }

3. 代码核心解释

（1）哈希集合的作用

• unordered_set<int> num_set：存储数组所有元素，自动去重（比如示例 3 的[1,0,1,2]会存为{0,1,2}），且查询操作count()的时间复杂度为 O (1)。

（2）「起点判断」的关键逻辑

if (!num_set.count(num - 1)) { ... }

• 只有当num-1不在集合中时，num才是连续序列的第一个数（比如1的0不存在，是起点；2的1存在，不是起点）。
• 这个判断能避免重复计算：比如序列1,2,3,4，只会从1开始遍历，2/3/4都会被跳过，保证整体时间复杂度为 O (n)（每个元素最多被访问两次：一次遍历，一次在 while 循环中）。

（3）统计连续长度

while (num_set.count(current_num + 1)) { current_num += 1; current_len += 1; }

• 从起点num开始，不断找num+1、num+2... 直到不存在，统计当前连续序列的长度。
• 用max(max_len, current_len)更新全局最长长度。

4. 为什么不能先排序？

你提到的「存入哈希表后排序」思路，时间复杂度会变成 O (n log n)（排序的时间），不符合题目要求的 O (n)。

• 比如对unordered_set排序，需要先转成数组，再调用sort()，时间复杂度 O (n log n)，会超时（数组长度 10⁵ 时，O (n log n) 比 O (n) 慢一个数量级）。

5. 边界情况处理

• 空数组：nums.length == 0时，直接返回 0（代码中max_len初始为 0，无需额外处理）。
• 单元素数组：比如[5]，返回 1。
• 重复元素：比如[1,1,1]，哈希集合去重后为{1}，返回 1。

总结

1. 核心思路：用哈希集合去重 + 只从「连续序列起点」开始统计长度，保证 O (n) 时间复杂度。
2. 关键优化：!num_set.count(num - 1)避免重复遍历，是实现 O (n) 的核心。
3. 复杂度：时间 O (n)（每个元素最多访问两次），空间 O (n)（哈希集合存储所有元素）。

5 小结

我觉得不太难，但是写不出来，又都是看题解的，这两题要掌握好set，要去重。

坚持，加油！！！！