leetcode筆記：Contains Duplicate II

leetcode筆記：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.

二. 題目分析

題目的大意是，給定一個整數數組與一個整數k，當且僅當存在兩個不同的下標i和j，滿足：nums[i] = nums[j]，且| i - j | <= k時返回true，反之返回false。

此題在前面一題Contains Duplicate的基礎上，要求兩個重復元素的下標相差不超過k。與上題的解法類似，令map中元素的值為key，元素下標為value，遍歷數組。當找到重復元素時，判斷兩個元素的下標差是否小於等於k。若大於k，更新已在map中元素對應的value，即下標的值。

三. 示例代碼

class Solution {
public:
    bool containsNearbyDuplicate(vector& nums, int k) {
        if (nums.size() < 2 || k < 1) return false;
        unordered_map numsMap;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (numsMap.count(nums[i]) == true)
            {
                if (i - numsMap[nums[i]] <= k)
                    return true;
                else numsMap[nums[i]] = i;
            }
            numsMap.insert(pair(nums[i], i));
        }
        return false;
    }
};

四. 小結

該題目使用unordered_map比map效率高。後續題目有：Contains Duplicate III。