【leetcode刷题】T38-存在重复元素 III
【英文题目】（学习英语的同时，更能理解题意哟~）
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolutedifference between i and j is at most k.
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
【中文题目】
给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。
示例 1:
输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
【思路】
本题与【T36-存在重复元素】【T37-存在重复元素 II】类似。
暴力破解很容易想到，循环遍历，比较两元素差值是否在给定范围即可。这种方法超时。
字典的方法，key为元素，value为元素所在位置。遍历数组元素e时，判断e-t -> e+t是否存在于字典中，存在即返回true。但是，当t过大时耗费大量时间，所以，t比字典元素个数大时，可以直接遍历所有字典元素，而不是遍历判断e-t -> e+t是否存在于字典中。
注意：c++由于int类型有取值范围，注意越界问题！（可以转换为long类型）
【代码】
python版本
class Solution(object):
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
d = {}
for i, n in enumerate(nums):
# 字典元素较少，只遍历字典更加节省时间
if len(d) < t:
for dk, dv in d.items():
if abs(n - dk) <= t and i - dv <= k:
return True
else:
for ti in range(t+):
if n+ti in d and i - d[n+ti] <= k:
return True
if n-ti in d and i - d[n-ti] <= k:
return True
d[n] = i
return False
C++版本
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
map<long, int> d;
map<long, int>::iterator it;
for(int i=; i<nums.size(); i++){
if(d.size() < t){
for(it=d.begin(); it!=d.end(); it++){
if(abs((long)nums[i] - it->first) <= t && (i - it->second) <= k)
return true;
}
}else{
for(int ti=; ti <= t; ti++){
if(d.find((long)nums[i] - ti) != d.end() && i - d[(long)nums[i] - ti] <= k)
return true;
if(d.find((long)nums[i] + ti) != d.end() && i - d[(long)nums[i] + ti] <= k)
return true;
}
}
d[(long)nums[i]] = i;
}
return false;
}
};本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-04-15，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读