欢迎访问LeetCode题解合集

题目描述

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

示例 2:

输入: nums = [1,0,1,1], k = 1
输出: true

示例 3:

输入: nums = [1,2,3,1,2,3], k = 2
输出: false

题解：

哈希表 unordered_map 。

从左往右遍历 nums ，插入每个元素的值和位置，如果当前元素 nums[i] 出现在哈希表中，判断它们的距离，不超过 k 直接返回 true ，否则更新哈希表中的距离。

时间复杂度：$O(n)$

额外空间复杂度：$O(n)$

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for ( int i = 0; i < nums.size(); ++i ) {
            if ( hash.count(nums[i]) && (i - hash[nums[i]] <= k) )
                return true;
            hash[nums[i]] = i;
        }
        return false;
    }
};
/*
时间：28ms，击败：90.29%
内存：16MB，击败：74.88%
*/