LeetCode 219、存在重复元素II

一、题目描述

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

示例 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

提示：

• 1 <= nums.length <= 10^5
• -109 <= nums[i] <= 10^9
• 0 <= k <= 10^5

二、题目解析

三、参考代码

Python

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:

        # 使用哈希集合
        pos = {}

        # 如果想在 for 循环中同时获得列表的索引 i 和元素值 v
        # 可以使用枚举内置函数 enumerate()
        for i, v in enumerate(nums):
            # 1、如果发现当前这个元素 v 已经存在于哈希集合里面
            # 说明在此之前就已经访问到了一个元素，值为 v
            # 2、pos[v] 表示的是之前访问到的元素值所在的索引
            # 判断 i - pos[v] <= k
            if v in pos and i - pos[v] <= k:
                # 符合要求，就返回 True
                return True
            # 否则，把 v 和 i 存储到哈希集合里面
            pos[v] = i

        # 最终没有找到，返回 False
        return False

Java

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {

        // 使用哈希集合
        Map<Integer, Integer> pos = new HashMap<>();

        // 如果想在 for 循环中同时获得列表的索引 i 和元素值 v
        // 可以使用枚举内置函数 enumerate()
        for (int i = 0; i < nums.length; i++) {
            int v = nums[i];
            
            // 1、如果发现当前这个元素 v 已经存在于哈希集合里面
            // 说明在此之前就已经访问到了一个元素，值为 v
            // 2、pos.get(v) 表示的是之前访问到的元素值所在的索引
            // 判断 i - pos.get(v) <= k
            if (pos.containsKey(v) && i - pos.get(v) <= k) {
                // 符合要求，就返回 True
                return true;
            }
            // 否则，把 v 和 i 存储到哈希集合里面
            pos.put(v, i);
        }

        // 最终没有找到，返回 False
        return false;
    }
}

C++

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {

        // 使用哈希集合
        unordered_map<int, int> pos;

        // 如果想在 for 循环中同时获得列表的索引 i 和元素值 v
        for (int i = 0; i < nums.size(); i++) {
            int v = nums[i];
            
            // 1、如果发现当前这个元素 v 已经存在于哈希集合里面
            // 说明在此之前就已经访问到了一个元素，值为 v
            // 2、pos[v] 表示的是之前访问到的元素值所在的索引
            // 判断 i - pos[v] <= k
            if (pos.count(v) && i - pos[v] <= k) {
                // 符合要求，就返回 true
                return true;
            }
            // 否则，把 v 和 i 存储到哈希集合里面
            pos[v] = i;
        }

        // 最终没有找到，返回 false
        return false;
    }
};

C

// 哈希表节点结构体
typedef struct HashNode {
    int key;
    int value;
    struct HashNode* next;
} HashNode;

// 哈希表结构体
typedef struct {
    HashNode** table;
    int size;
} HashMap;

// 创建哈希表
HashMap* createHashMap(int size) {
    HashMap* map = (HashMap*)malloc(sizeof(HashMap));
    map->table = (HashNode**)calloc(size, sizeof(HashNode*));
    map->size = size;
    return map;
}

// 哈希函数
int hashFunction(int key, int size) {
    return (key % size + size) % size;
}

// 查找哈希表中的键
HashNode* find(HashMap* map, int key) {
    int index = hashFunction(key, map->size);
    HashNode* node = map->table[index];
    while (node) {
        if (node->key == key) {
            return node;
        }
        node = node->next;
    }
    return NULL;
}

// 插入或更新哈希表中的键值对
void put(HashMap* map, int key, int value) {
    int index = hashFunction(key, map->size);
    HashNode* node = find(map, key);
    if (node) {
        node->value = value;
    } else {
        HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
        newNode->key = key;
        newNode->value = value;
        newNode->next = map->table[index];
        map->table[index] = newNode;
    }
}

// 释放哈希表
void freeHashMap(HashMap* map) {
    for (int i = 0; i < map->size; i++) {
        HashNode* node = map->table[i];
        while (node) {
            HashNode* temp = node;
            node = node->next;
            free(temp);
        }
    }
    free(map->table);
    free(map);
}

// 主函数
bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
    HashMap* map = createHashMap(numsSize);

    for (int i = 0; i < numsSize; i++) {
        HashNode* node = find(map, nums[i]);
        if (node && i - node->value <= k) {
            freeHashMap(map);
            return true;
        }
        put(map, nums[i], i);
    }

    freeHashMap(map);
    return false;
}

Node JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    // 使用哈希表存储元素值和其索引
    const pos = new Map();

    for (let i = 0; i < nums.length; i++) {
        const v = nums[i];
        // 如果当前元素已经存在于哈希表中并且索引差值小于等于 k
        if (pos.has(v) && i - pos.get(v) <= k) {
            return true;
        }
        // 更新当前元素的索引
        pos.set(v, i);
    }

    return false;
};

Go

func containsNearbyDuplicate(nums []int, k int) bool {
    // 使用 map 存储元素值及其索引
    pos := make(map[int]int)

    for i, v := range nums {
        // 如果当前元素已经存在并且索引差值小于等于 k
        if idx, found := pos[v]; found && i-idx <= k {
            return true
        }
        // 更新当前元素的索引
        pos[v] = i
    }

    return false
}