【leetcode刷题】T37-存在重复元素 II
【英文题目】（学习英语的同时，更能理解题意哟~）
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between iand j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true
【中文题目】
给定一个整数数组和一个整数 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
【思路】
本题与【T36-存在重复元素】类似，两种方法：一是暴力破解，二是使用hash表。
暴力破解：使用两层for循环，查找是否有元素满足条件。
hash表：key为元素，value为元素的下标，当某个元素存在hash表中，则判断是否满足条件，如果不满足，则更新value值。
【代码】
python版本
class Solution(object):
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
d = {}
for i, n in enumerate(nums):
if n in d and i - d[n] <= k:
return True
d[n] = i
return False
C++版本
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
map<int, int> d;
for(int i=; i<nums.size(); i++){
if(d.find(nums[i]) != d.end() && i - d[nums[i]] <= k)
return true;
d[nums[i]] = i;
}
return false;
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读