哈希算法题目：存在重复元素 II
字数 2189 2025-10-25 22:15:07

哈希算法题目：存在重复元素 II

题目描述
给定一个整数数组 nums 和一个整数 k，请判断数组中是否存在两个不同的索引 i 和 j，使得 nums[i] = nums[j]，并且 i 和 j 的绝对差至多为 k（即 |i - j| <= k）。

解题过程

  1. 问题理解
    这个问题的核心是：在数组中寻找重复出现的数字，但这次我们关心的不是数字本身是否重复，而是重复出现的位置是否足够"近"。具体来说，我们需要找到两个相同的数字，并且它们所在的位置索引之差不能超过给定的 k。如果存在这样一对数字，返回 true；否则返回 false。

  2. 初步思路
    一个最直接的想法是使用双重循环：

    • 外层循环遍历数组中的每一个元素 nums[i]。
    • 内层循环从 i+1 开始，遍历到 i+k 的位置（注意不要超出数组边界）。
    • 检查 nums[i] 是否等于内层循环遍历到的元素 nums[j]。如果相等，则立即返回 true。
    • 如果所有循环都结束了也没有找到满足条件的元素对，则返回 false。
    • 缺点：当 k 的值很大，甚至接近数组长度 n 时，这种方法的时间复杂度会接近 O(n²)，效率较低。

  3. 优化思路：引入哈希表
    为了提升效率，我们需要避免内层的循环。哈希表（在 Python 中是字典 dict）可以帮助我们以接近 O(1) 的时间复杂度存储和查找元素。我们可以利用它来记录每个数字最近一次出现的索引位置。

    • 核心思想：当我们遍历数组时，对于当前遇到的数字 num，我们查看哈希表，看这个数字之前是否出现过。
      • 如果没有出现过，我们就将 (数字：当前索引) 这个键值对存入哈希表。
      • 如果出现过，我们就计算当前索引和哈希表中记录的该数字的上一个索引的差值。
        • 如果这个差值 <= k，那么我们就找到了满足条件的元素对，返回 true。
        • 如果这个差值 > k，说明之前出现的那个位置离得太远了，不符合"至多为 k"的要求。但是，当前这个新位置可能离它后面出现的相同数字更近。因此，我们需要更新哈希表，将这个数字对应的值（索引）更新为当前索引。因为对于后续的遍历来说，当前索引是离它们"更近"的参考点。

  4. 详细步骤（使用哈希表）
    让我们一步步模拟这个过程。假设 nums = [1, 2, 3, 1, 2, 3], k = 2。

    • 初始化一个空的哈希表 num_index_map = {}。
    • 开始遍历数组，索引 i 从 0 开始：
      • i = 0, num = 1：哈希表中没有 1。将 (1: 0) 存入哈希表。此时哈希表：{1: 0}。
      • i = 1, num = 2：哈希表中没有 2。将 (2: 1) 存入哈希表。此时哈希表：{1: 0, 2: 1}。
      • i = 2, num = 3：哈希表中没有 3。将 (3: 2) 存入哈希表。此时哈希表：{1: 0, 2: 1, 3: 2}。
      • i = 3, num = 1：哈希表中有 1，其记录的索引是 0。计算差值 |3 - 0| = 3。判断 3 > k(2)？是的，所以不返回 true。但是，我们需要更新哈希表中 1 的索引为当前索引 3。此时哈希表：{1: 3, 2: 1, 3: 2}。（注意，键 1 的值从 0 更新为 3）。
      • i = 4, num = 2：哈希表中有 2，其记录的索引是 1。计算差值 |4 - 1| = 3。判断 3 > k(2)？是的，所以不返回 true。更新哈希表中 2 的索引为当前索引 4。此时哈希表：{1: 3, 2: 4, 3: 2}。
      • i = 5, num = 3：哈希表中有 3，其记录的索引是 2。计算差值 |5 - 2| = 3。判断 3 > k(2)？是的，所以不返回 true。更新哈希表中 3 的索引为当前索引 5。此时哈希表：{1: 3, 2: 4, 3: 5}。
    • 遍历结束，没有找到满足条件的元素对，返回 false。

  5. 算法总结

    • 数据结构：一个哈希表（字典），用于存储数字 -> 该数字最近一次出现的索引。
    • 算法流程：
      1. 初始化一个空哈希表 map。
      2. 使用 i 作为索引，从头到尾遍历数组 nums。
      3. 对于每个元素 num = nums[i]：
        a. 检查 num 是否存在于 map 中。
        b. 如果存在，取出其值 prev_index（即上次出现的索引），计算 i - prev_index，如果结果 <= k，则返回 true。
        c. 无论差值是否小于等于 k，都要执行这一步：将 map[num] 的值更新为当前的索引 i。（这一步确保了哈希表里记录的永远是最近一次出现的索引，为后续的比较提供了最近的可能）。
      4. 如果遍历完整个数组都没有返回 true，则返回 false。
    • 时间复杂度：O(n)，我们只遍历了一次数组，每次对哈希表的操作都是 O(1)。
    • 空间复杂度：O(n)，最坏情况下（所有数字都不重复），哈希表需要存储 n 个键值对。
哈希算法题目：存在重复元素 II 题目描述 给定一个整数数组 nums 和一个整数 k，请判断数组中是否存在两个不同的索引 i 和 j，使得 nums[ i] = nums[ j]，并且 i 和 j 的绝对差至多为 k（即 |i - j| <= k）。 解题过程 问题理解 这个问题的核心是：在数组中寻找重复出现的数字，但这次我们关心的不是数字本身是否重复，而是重复出现的位置是否足够"近"。具体来说，我们需要找到两个相同的数字，并且它们所在的位置索引之差不能超过给定的 k。如果存在这样一对数字，返回 true；否则返回 false。 初步思路 一个最直接的想法是使用双重循环： 外层循环遍历数组中的每一个元素 nums[i] 。 内层循环从 i+1 开始，遍历到 i+k 的位置（注意不要超出数组边界）。 检查 nums[i] 是否等于内层循环遍历到的元素 nums[j] 。如果相等，则立即返回 true。 如果所有循环都结束了也没有找到满足条件的元素对，则返回 false。 缺点 ：当 k 的值很大，甚至接近数组长度 n 时，这种方法的时间复杂度会接近 O(n²)，效率较低。 优化思路：引入哈希表 为了提升效率，我们需要避免内层的循环。哈希表（在 Python 中是字典 dict ）可以帮助我们以接近 O(1) 的时间复杂度存储和查找元素。我们可以利用它来记录每个数字 最近一次出现 的索引位置。 核心思想 ：当我们遍历数组时，对于当前遇到的数字 num ，我们查看哈希表，看这个数字之前是否出现过。 如果 没有出现过 ，我们就将 (数字：当前索引) 这个键值对存入哈希表。 如果 出现过 ，我们就计算当前索引和哈希表中记录的该数字的上一个索引的差值。 如果这个差值 <= k ，那么我们就找到了满足条件的元素对，返回 true。 如果这个差值 > k ，说明之前出现的那个位置离得太远了，不符合"至多为 k"的要求。但是，当前这个新位置可能离它后面出现的相同数字更近。因此，我们需要 更新哈希表 ，将这个数字对应的值（索引）更新为 当前索引 。因为对于后续的遍历来说，当前索引是离它们"更近"的参考点。 详细步骤（使用哈希表） 让我们一步步模拟这个过程。假设 nums = [1, 2, 3, 1, 2, 3] , k = 2 。 初始化一个空的哈希表 num_index_map = {} 。 开始遍历数组，索引 i 从 0 开始： i = 0 , num = 1 ：哈希表中没有 1 。将 (1: 0) 存入哈希表。此时哈希表： {1: 0} 。 i = 1 , num = 2 ：哈希表中没有 2 。将 (2: 1) 存入哈希表。此时哈希表： {1: 0, 2: 1} 。 i = 2 , num = 3 ：哈希表中没有 3 。将 (3: 2) 存入哈希表。此时哈希表： {1: 0, 2: 1, 3: 2} 。 i = 3 , num = 1 ：哈希表中有 1 ，其记录的索引是 0 。计算差值 |3 - 0| = 3 。判断 3 > k(2) ？是的，所以不返回 true。但是，我们需要 更新 哈希表中 1 的索引为当前索引 3 。此时哈希表： {1: 3, 2: 1, 3: 2} 。（注意，键 1 的值从 0 更新为 3 ）。 i = 4 , num = 2 ：哈希表中有 2 ，其记录的索引是 1 。计算差值 |4 - 1| = 3 。判断 3 > k(2) ？是的，所以不返回 true。 更新 哈希表中 2 的索引为当前索引 4 。此时哈希表： {1: 3, 2: 4, 3: 2} 。 i = 5 , num = 3 ：哈希表中有 3 ，其记录的索引是 2 。计算差值 |5 - 2| = 3 。判断 3 > k(2) ？是的，所以不返回 true。 更新 哈希表中 3 的索引为当前索引 5 。此时哈希表： {1: 3, 2: 4, 3: 5} 。 遍历结束，没有找到满足条件的元素对，返回 false。 算法总结 数据结构 ：一个哈希表（字典），用于存储 数字 -> 该数字最近一次出现的索引 。 算法流程 ： 初始化一个空哈希表 map 。 使用 i 作为索引，从头到尾遍历数组 nums 。 对于每个元素 num = nums[i] ： a. 检查 num 是否存在于 map 中。 b. 如果存在，取出其值 prev_index （即上次出现的索引），计算 i - prev_index ，如果结果 <= k ，则返回 true 。 c. 无论差值是否小于等于 k ，都要执行这一步：将 map[num] 的值更新为当前的索引 i 。（这一步确保了哈希表里记录的永远是最近一次出现的索引，为后续的比较提供了最近的可能）。 如果遍历完整个数组都没有返回 true ，则返回 false 。 时间复杂度 ：O(n)，我们只遍历了一次数组，每次对哈希表的操作都是 O(1)。 空间复杂度 ：O(n)，最坏情况下（所有数字都不重复），哈希表需要存储 n 个键值对。