LeetCode 219. Contains Duplicate II

題目

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

翻譯

給一個陣列nums跟一個整數k，判斷能不能在陣列中找到nums[i] = numsj，而且i跟j的距離不能比k還大。

範例:
nums = [1,2,3,4,1] k=3; nums[0] = nums[4] = 1 , j=4, i=0, i,j距離為4比k還大，因此為false nums = [1,2,3,4,1] k=4; nums[0] = nums[4] = 1 , j=4, i=0, i,j距離為4沒有比k大，因此為true

思路

1. 使用一個map存放出現過的數字以及位置
2. 如果出現重複的數字，判斷目前位置與儲存的位置距離是否小於等於k，有的話直接回傳true
3. 陣列中沒有符合的配對，回傳false

解題

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    if(nums.length <= 1) return false;

    // 使用map儲存出現過的數字
    var map = {};

    for(var i in nums){
        var v = nums[i];

        if(map[v] && (i - map[v] <= k)){
            // 如果有出現重複的數字，判斷目前的位置-之前儲存的位置 <= k，符合條件return true
            return true;
        }
        // 將出現過的數字與其位置放入map
        map[v] = i;
    }

    // 全部跑完，沒符合條件的配對，return false
    return false;
};