Leetcode题目链接：219. 存在重复元素 II

题目描述：

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

解题思路：

• 暴力遍历判断：

  • 使用循环嵌套进行遍历，对于索引相等的情况直接跳过(特殊情况)，对元素大小以及位置进行比较(效率较低 见我的答案)

  • 使用循环嵌套进行遍历，内层循环从外层循环的后一位开始遍历，在循环条件中定义abs(i - j) <= k 的条件，把索引绝对值作为判断循环条件,减少循环次数(效率有所提高 见正确答案)

• 哈希表：

  • 循环遍历过程中记录每个数字出现的位置，当该数字再次出现时比较哈希表中存放的位置，满足条件即返回true，否则记录当前指针的位置

我的答案：

class Solution {
public:
    int abs(int x,int y){
        return x >= y ? x - y : y - x;
    }
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(i == j)continue;
                if(nums[i] == nums[j] && abs(i,j) <= k )return true;
            }
        }
        return false;
    }
};

提交结果：

正确答案：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n && j - i <= k; j++){
                if(nums[i] == nums[j])return true;
            }
        }
        return false;
    }
};

提交结果：

官方答案：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> dictionary;
        int length = nums.size();
        for (int i = 0; i < length; i++) {
            int num = nums[i];
            if (dictionary.count(num) && i - dictionary[num] <= k) {
                return true;
            }
            dictionary[num] = i;
        }
        return false;
    }
};

作者：力扣官方题解
链接：https://leetcode.cn/problems/contains-duplicate-ii/solutions/1218075/cun-zai-zhong-fu-yuan-su-ii-by-leetcode-kluvk/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。