LeetCode 219:Contins Duplicate II

Gven an array of integers and an integer k,find out whethere there re re re two distinct i and j in the array such that nums[i]=nums[j]and the difference between and j most k.
直接使用循環時間の複雑さはO(N＊k)であり、stlにおけるマゼンタによるサイクル時間を減らすことができ、O(logN)の時間複雑度の中で要素を見つけたり、hashテーブルによるunorderd(u)をさらに使うことができる.mapは、定数時間内に要素を見つける.この問題で学んだ二つの経験:

定数時間内でクエリー作業を完了したい場合、hashテーブルを考慮する.

stlには、hashテーブルで実現されるデータ構造mapとsetがあるので、hashテーブルクエリの特徴も残しています.

コードは以下の通りです

class Solution {
public:

/*    ：   bool containsNearbyDuplicate(vector<int>& nums, int k) { int length=nums.size(); if(length<=1||k<=0) return false; //          k        for(int i=0;i<length;i++) { for(int j=1;j<=k&&(i+j)<length;j++) { if(nums[i]==nums[i+j]) return true; } } return false; } */


   //   ，  stl  map，            
    bool containsNearbyDuplicate(vector<int>& nums, int k) 
    {
        //        map，   96ms,   map   unordered_map     32ms
        unordered_map<int ,int> maps;
        int length=nums.size();
        for(int i=0;i<length;i++)
        {
            if(maps.count(nums[i]))//   maps       ，            k
            {
                if((i-maps[nums[i]])<=k) 
                    return true;
            }
            maps[nums[i]]=i;
        }
        return false;
    }

};