2022-11-17
Leetcode
00

目录

1. 题目
2. 解一
3. 优化

1. 题目

给定一个整数数组和一个整数 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

2. 解一

# 217. 存在重复元素差不多,维护一个哈希表,只不过这次存储的是下标,当遇到相同值是判断两个下标差是否小于k

javascript
/** * @param {number[]} nums * @param {number} k * @return {boolean} */ var containsNearbyDuplicate = function(nums, k) { const hashArr = [] for(let i in nums) { if(hashArr[nums[i]] === undefined) { hashArr[nums[i]] = i } else { if(i - hashArr[nums[i]] <= k) { return true } else { hashArr[nums[i]] = i } } } return false };

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

image.png

3. 优化

数组改用Set 每次往Set中Push一个新值,Set的长度始终维持在小于k,如果新的值有在Set中,则直接返回

javascript
/** * @param {number[]} nums * @param {number} k * @return {boolean} */ var containsNearbyDuplicate = function(nums, k) { const set = new Set() for(let i in nums) { if(set.has(nums[i])) { return true } set.add(nums[i]) if(set.size > k) { set.delete(nums[i - k]) } } return false };

复杂度分析

  • 时间复杂度:O(n)
  • 空间复杂度:O(k)

image.png

如果对你有用的话,可以打赏哦
打赏
ali pay
wechat pay

本文作者:叶继伟

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!