专栏首页脑洞前端219. 存在重复元素 II

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/contains-duplicate-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

由于题目没有对空间复杂度有求,用一个hashmap 存储已经访问过的数字即可, 每次访问都会看hashmap中是否有这个元素,有的话拿出索引进行比对,是否满足条件(相隔不大于k),如果满足返回true即可。

关键点解析

代码

/*
 * @lc app=leetcode id=219 lang=javascript
 *
 * [219] Contains Duplicate II
 *
 * https://leetcode.com/problems/contains-duplicate-ii/description/
 *
 * algorithms
 * Easy (34.75%)
 * Total Accepted:    187.3K
 * Total Submissions: 537.5K
 * Testcase Example:  '[1,2,3,1]\n3'
 *
 * 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 i and 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
 *
 *
 *
 * Example 3:
 *
 *
 * Input: nums = [1,2,3,1,2,3], k = 2
 * Output: false
 *
 *
 *
 *
 *
 */
/**
 * @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
};

本文分享自微信公众号 - 脑洞前端(fe_lucifer),作者:脑洞很大的程序员

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

原始发表时间:2019-08-18

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 75. 颜色分类

    给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

    lucifer210
  • 283. 移动零

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

    lucifer210
  • 47. 全排列 II

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/permutations-ii 著作权归领扣网络所有。商...

    lucifer210
  • LeetCode 283. 移动零

    给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

    freesan44
  • Q189 Rotate Array

    Rotate an array of n elements to the right by k steps. For example, with n = 7 a...

    echobingo
  • LeetCode 280. Wiggle Sort IIsolution

    复杂度 时间 O(N) 空间 O(1) 思路 题目对摇摆排序的定义有两部分: 如果i是奇数,nums[i] >= nums[i - 1] 如果i是偶数...

    desperate633
  • [Leetcode][python]删除排序数组中的重复项/删除排序数组中的重复项 II

    数组完成排序后,我们可以放置两个指针 ii 和 jj,其中 ii 是慢指针,而 jj 是快指针。只要 nums[i] = nums[j]nums[i]=nums...

    后端技术漫谈
  • 丢失的数字

    给定一个包含 [0, n] 中 n 个数的数组 nums ,找出 [0, n] 这个范围内没有出现在数组中的那个数。

    _kyle
  • LeetCode140|有多少小于当前数字的数字

    给你一个数组 nums,对于其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目。

    码农王同学
  • 018. 四数之和 | Leetcode题解

    给定一个包含n 个整数的数组 nums 和一个目标值 target ,判断 nums 中是否存在四个元素 a, b,c 和 d ,使得a + b + c ...

    苏南

扫码关注云+社区

领取腾讯云代金券