Links

0219. 存在重复元素 II

题目地址(219. 存在重复元素 II)

https://leetcode-cn.com/problems/contains-duplicate-ii/

题目描述

给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的 绝对值 至多为 k。
 
示例 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

前置知识

  • hashmap

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

用一个 hashmap 存储已经访问过的数字,每次访问都查看 hashmap 中是否有这个元素,有的话拿出索引进行比对,是否满足条件(相隔不大于 k),如果满足返回 true 即可。
可以看出,这道题就是两数和的进阶版。大家可以将这两道题结合起来理解哦~

公司

  • airbnb
  • palantir

关键点解析

  • 空间换时间

代码

  • 语言支持:JS,Python,C++, Java
Javascript Code:
/**
* @param {number[]} nums
* @param {number} k
* @return {boolean}
*/
var containsNearbyDuplicate = function (nums, k) {
const visited = {};
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
if (visited[num] !== undefined && i - visited[num] <= k) {
return true;
}
visited[num] = i;
}
return false;
};
Python Code:
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
d = {}
for index, num in enumerate(nums):
if num in d and index - d[num] <= k:
return True
d[num] = index
return False
C++ Code:
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
auto m = unordered_map<int, int>();
for (int i = 0; i < nums.size(); ++i) {
auto iter = m.find(nums[i]);
if (iter != m.end()) {
if (i - m[nums[i]] <= k) {
return true;
}
}
m[nums[i]] = i;
}
return false;
}
};
Java Code:
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int i=0;i<nums.length;i++)
{
if(map.get(nums[i]) != null && (i-map.get(nums[i])) <= k)
{
return true;
}
map.put(nums[i], i);
}
return false;
}
}
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$
更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。
关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。