Leetcode219_Contains_DuplicateII

• 題目

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 absolute difference between i and j is at most k.

• 翻譯

給定一個整數數組和一個整數k，找出是不是存在兩個不同的索引i和j在這個數組中，使得nums[i]==nums[j],并且i和j的絕對差距最大是k。

• 題解

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

        //使用一個set記錄出現過的元素
        set<int> record;
        for ( int i = ; i < nums.size() ; i++ )
        {
            //如果record中記錄過目前元素，則說明該元素之前存在過，在k的距離内，有一個元素和該元素相等
            if ( record.find(nums[i]) != record.end() )
                return true;
            // 插入目前元素
            record.insert( nums[i] );

            //當record的大小達到k的時候，删除掉視窗最左邊的元素
            if ( record.size() == k +  )
                record.erase( nums[i-k] );
        }

        return false;

    }
};