专栏首页木又AI帮【leetcode刷题】T38-存在重复元素 III

【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

【中文题目】

给定一个整数数组,判断数组中是否有两个不同的索引 ij,使得 nums [i]nums [j] 的差的绝对值最大为 t,并且 ij 之间的差的绝对值最大为 ķ

示例 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;
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T34-只出现一次的数字 II

    Given a non-empty array of integers, every element appears three times except fo...

    木又AI帮
  • 【leetcode刷题】T162-打家劫舍 II

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有...

    木又AI帮
  • 【更新】【leetcode刷题】T35-只出现一次的数字 III

    Given an array of numbers nums, in which exactly two elements appear only once a...

    木又AI帮
  • 【LeetCode】旋转数组

    韩旭051
  • 力扣198——打家劫舍

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小...

    健程之道
  • Leetcode 47. Permutations II

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • 我刻意练习了很久才有那么一点自信

    关于算法题的做法,自己也很少去看,也很少去做,所以这里自己也是一位算法做题的"萌新",还记得大学时自己买过一本关于算法题的书,有的时候还会翻翻这本书,但是这本书...

    后端Coder
  • Leetcode 46. Permutations

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • LeetCode - 最接近的三数之和

    原题地址:https://leetcode-cn.com/problems/3sum-closest/

    晓痴
  • leetcode 27 Remove Element

    @坤的

扫码关注云+社区

领取腾讯云代金券