「力扣」第 219 题: 存在重复元素 II(中等)

liweiwei1419 ... 2021-12-26 哈希表
  • 哈希表
About 2 min

# 题目描述

给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 ij,使得 nums [i] = nums [j],并且 ij 的差的绝对值最大为 k

示例 1:

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

示例 2:

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

示例 3:

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

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 0 <= k <= 10^5

# 思路分析

如果你做过 「力扣」第 1 题: 两数之和 (opens new window),这道题就变得很容易了。

1、判定重复元素,首先我们会想到使用哈希表;

2、题目又要求“ ij 的差的绝对值最大为 k”,因此,哈希表的 key 为数组元素,value 为其对应的索引;

3、“是否存在问题”的做法是:在遍历的过程中找到就直接返回,如果找不到,才返回 false。因此找到(或者说存在)的充分必要条件是:

找到重复元素的索引与之前出现过的这个元素的索引的差小于等于 k,后出现的数的索引一定比前出现的数的索引大,因此绝对值不用考虑。

参考代码

复杂度分析:

  • 时间复杂度:O(N)O(N),这里 NN 是数组的元素个数,算法遍历了一次数组;
  • 空间复杂度:O(N)O(N),这里使用了哈希表存储已经出现的数,可以说是以空间换时间了。
Last update: January 14, 2022 00:02
Contributors: liweiwei1419