leetCode EASY - Q219.Contains Duplicate 2
===

---
###### tags: `leetCode`, `練習刷題`, `219`

<br>

## 題目
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= 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

## 理解
我們需要做一個函式來檢查一個數組 nums 中國年是否存在兩個相同的數，且這兩個數的索引之差的絕對值不大於給定的距離 *k* 。

意思說首先，array裡要有同樣的值，不然也會 回傳false。且這兩個數的索引之差的絕對值不大於給定的*k*。

## 解法

function containsNearbyDuplicate(nums:number[], k:number ){
    const seen ={};
    for(let i = 0 ; i < nums.length ; i++){
        const num = nums[i];
        if(num in seen && i - seen[num] <= k){
            return true;
        }
        seen[num] = i; 
    }
    return false;
}

1. *seen* 用來記錄每個數字最後一次出現的索引位置。
2. 函式遍歷 *nums* 時，會檢查當前數字是否之前出現過，並且當前索引 *i* 漸趨這個數字之前儲存的索引是否小於 *k*
3. 如果這兩個條件滿足，說明在允許的距離內找到了一個重複的數字，就 return true。反則 return false。
4. 意思是說：

初始化
seen = {}：一開始，seen 對象是空的。

第一次迴圈：i = 0
num = nums[0] = 1
檢查 seen：此時 seen 是空的，所以 1 還沒有被記錄過。
更新 seen：seen = {1: 0}（數字 1 現在記錄為在索引 0 出現）。

第二次迴圈：i = 1
num = nums[1] = 2
檢查 seen：2 沒有在 seen 中。
更新 seen：seen = {1: 0, 2: 1}（數字 2 現在記錄為在索引 1 出現）。

第三次迴圈：i = 2
num = nums[2] = 3
檢查 seen：3 沒有在 seen 中。
更新 seen：seen = {1: 0, 2: 1, 3: 2}（數字 3 現在記錄為在索引 2 出現）。

第四次迴圈：i = 3
num = nums[3] = 1
檢查 seen：1 在 seen 中，且上一次出現在索引 0。
計算 i - seen[1] = 3 - 0 = 3
檢查條件：i - seen[num] <= k => 3 <= 3 是 true。

---
## 別人的解法：

function containsNearbyDuplicate(nums, k) {
    // 建立一個雜湊表來存儲元素及其索引
    let elementIndices = new Map();
    
    // 遍歷陣列
    for (let i = 0; i < nums.length; i++) {
        let num = nums[i];
        // 如果當前元素已經在雜湊表中
        if (elementIndices.has(num)) {
            // 檢查當前索引與之前索引的絕對差是否小於等於 k
            if (Math.abs(i - elementIndices.get(num)) <= k) {
                return true;
            }
        }
        // 更新雜湊表,將當前元素及其索引存儲
        elementIndices.set(num, i);
    }
    
    // 如果找不到符合條件的重複元素,返回 false
    return false;
}

1. 初始化一個 *雜湊表* elementIndices 來存儲元素及其索引。
2. 遍歷輸入陣列 nums：
- 檢查 num 是否已經在雜湊表 elementIndices 中：
- 如果 num 在雜湊表中，則計算當前索引 i 與之前索引的絕對差值。
- 如果絕對差值小於等於 k， 那就return true，因為找到了一個對滿足條件的重複值
- 如果 num 不再雜湊表中，就將 num 及其索引 i 添加到雜湊表 elementIndices中。
3. 如果遍歷完整個陣列仍然沒有找到任何一堆滿足的條件的重複元素，就返回 false。

這個方法的關鍵在於使用 new Map() 來跟蹤元素以及索引。這樣可以在常熟時間內查找某個元素是否出現過，並且可以快速甲酸當前元素與之前出現的相同元素的索引差值。