「力扣」第 219 题: 存在重复元素 II(中等)
liweiwei1419 ... 2021-12-26 About 2 min
# 题目描述
给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。
示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true
1
2
2
示例 2:
输入: nums = [1,0,1,1], k = 1
输出: true
1
2
2
示例 3:
输入: nums = [1,2,3,1,2,3], k = 2
输出: false
1
2
2
Constraints:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5
# 思路分析
如果你做过 「力扣」第 1 题: 两数之和 (opens new window),这道题就变得很容易了。
1、判定重复元素,首先我们会想到使用哈希表;
2、题目又要求“ i
和 j
的差的绝对值最大为 k
”,因此,哈希表的 key 为数组元素,value 为其对应的索引;
3、“是否存在问题”的做法是:在遍历的过程中找到就直接返回,如果找不到,才返回 false
。因此找到(或者说存在)的充分必要条件是:
找到重复元素的索引与之前出现过的这个元素的索引的差小于等于
k
,后出现的数的索引一定比前出现的数的索引大,因此绝对值不用考虑。
参考代码:
复杂度分析:
- 时间复杂度:,这里 是数组的元素个数,算法遍历了一次数组;
- 空间复杂度:,这里使用了哈希表存储已经出现的数,可以说是以空间换时间了。