LeetCode #219 Contains Duplicate II 包含重複項目 II

英文原文如下

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.

中文翻譯

給予一個整數陣列 nums 跟 一個整數 k要是有兩個陣列中不同的索引 i 跟 j 對應的值相等,並且兩個索引相差必須小於等於 k ,則回傳 true

範例及題目限制


解題思路

這一題其實是之前寫過的 LeetCode #217 Contains Duplicate 包含重複項目 的進階

比起本來單純的找重複,這次加入了 index 的比較

故我們的解決方法也會調整,由之前的 單純判斷的HashSet升級為 Dictionary

Key 放的會是字符, Value 則是其最後出現的 index

C# 解決方案

方案1

public class Solution {
    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        Dictionary<int,int> dict =   new Dictionary<int,int>();

        for(int i = 0; i<nums.Length; i++)
        {
            if (!dict.ContainsKey(nums[i]))
            {
                dict.Add(nums[i], i);
            }
            else
            {
                if(i-dict[nums[i]]<=k)
                {
                    return true;
                }
                dict[nums[i]] = i;
            }
        }
        return false;
    }
}

Java解決方案

方案1

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer>map =   new HashMap<Integer,Integer>();

        for(int i = 0; i<nums.length; i++)
        {
            if (map.containsKey(nums[i]))
            {
                if(i-map.get(nums[i])<=k)
                {
                    return true;
                }   
            }
            map.put(nums[i],i);
        }
        return false;
    }
}

Python3 解決方案

方案1

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

        for i in range (len(nums)):
            if (nums[i] in dict):
                if(i-dict[nums[i]]<=k):
                    return True

            dict[nums[i]] = i
        return False

JavaScript 解決方案

方案1

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
        const map =   new Map();

        for(let i = 0; i<nums.length; i++)
        {
            if (map.has(nums[i]))
            {
                if(i-map.get(nums[i])<=k)
                {
                    return true;
                }   
            }
            map.set(nums[i],i);
        }
        return false;
};

結論

比起本來的題型,難度又高了一個層次吧

偷偷跟大家預告一聲,這個系列其實有3題,相比前兩題都是Easy,第三題直接被歸類為Hard!!

不過我也還沒特別看過,整理完後再跟各位介紹囉~

🧡如果這篇文章有幫上你的一點點忙,那是我的榮幸

🧡收藏文章或幫我點個廣告,那都是對我的支持

✅如有任何疑問,歡迎透過留言或messenger讓我知道 !

題目連結 : Contains Duplicate II – LeetCode

類似題目 : LeetCode #217 Contains Duplicate 包含重複項目

一些隨機的LeetCode文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *