leetcode219-存在重复元素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

解法

思想

哈希表,将元素和最后出现的下标对应起来,后面遍历到相同元素时看下标之差是否小于等于k

代码

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.containsKey(nums[i])){
                if(i-map.get(nums[i])<=k) return true;
            }
            map.put(nums[i],i);
        }
        return false;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode219-%e5%ad%98%e5%9c%a8%e9%87%8d%e5%a4%8d%e5%85%83%e7%b4%a0ii/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月23日
下一篇 2019年12月25日

相关推荐

  • leetcode234-回文链表

    原题 请判断一个链表是否为回文链表。 示例1: 输入: 1->2 输出: false 示例2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂…

    2019年12月16日
    0100
  • leetcode559-N叉树的最大深度

    原题 给定一个 N 叉树,找到其最大深度。 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 例如,给定一个 3叉树 : 我们应返回其最大深度,3。 说明: 树的深度不会…

    2020年1月20日
    050
  • leetcode128-最长连续序列

    原题 给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。 示例: 输入: [100, 4, 200, 1, 3, 2] 输出: 4 解释: 最长…

    算法 2020年6月6日
    080
  • leetcode994-腐烂的橘子

    原题 在给定的网格中,每个单元格可以有以下三个值之一: 值 0 代表空单元格;值 1 代表新鲜橘子;值 2 代表腐烂的橘子。每分钟,任何与腐烂的橘子(在 4 个正方向上)相邻的新鲜…

    2020年3月4日
    0100
  • leetcode160-相交链表

    原题 编写一个程序,找到两个单链表相交的起始节点。 如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入: intersectVal = 8, listA = [4,1,…

    2019年12月14日
    070
  • leetcode349-两个数组的交集

    原题 给定两个数组,编写一个函数来计算它们的交集。 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2] 示例2: 输入: nums1 = [4…

    算法 2019年12月14日
    080
  • leetcode13-罗马数字转整数

    原题 罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。 字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000 例如, 罗马数字 2…

    算法 2020年4月25日
    080
  • 剑指offer47-礼物的最大价值

    原题(来源Leetcode) 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一…

    算法 2020年6月12日
    080
  • leetcode3-无重复字符的最长子串

    原题 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长…

    2019年12月26日
    0100
  • leetcode1071-字符串的最大公因子

    原题 对于字符串 S 和 T,只有在 S = T + ... + T(T 与自身连接 1 次或多次)时,我们才认定 “T 能除尽 S”。 返回最长字符串 X,要求满足 X 能除尽 …

    算法 2020年3月12日
    0240

发表回复

登录后才能评论