[leetcode] 219 Contains Duplicate II(map)

考え方一:
mapマッピング<値、下付き>を使用して、出現したnums[i]を記録し、対応する位置iを記録する.衝突が発生した場合、両者の位置関係を比較し、差がk以下の場合、trueを返します.そうしないと、新しい位置に変更されます.競合がない場合は、重複要素は含まれていません.

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

     for(int i=0; i<nums.size(); i++)
     {
       if(mp.find(nums[i])!= mp.end() && i-mp[nums[i]] <= k)
         return true;
       else
         mp[nums[i]] = i;
     }
     return false;
  }
};

考え方2:
set検索の効率性と定長ウィンドウ思想を利用する.最大長kのスライドウィンドウを直接定義し、1つのsetメンテナンスウィンドウ内の数字で繰り返しが発生したかどうかを判断し、2つのポインタstartとendを使用してスライドウィンドウの両端をマークし、初期は0であり、その後endは絶えず拡張され、スキャン要素は繰り返し要素が現れたかどうかを判断し、end-start>kが発見されるまでstartを移動し、そしてsetで対応する要素を除去します.配列の最後までスキャンしても重複要素が見つからないと思ったらfalseを返すことができます.時間的複雑度も空間的複雑度もO(N)である.

class Solution
{
public:
  bool containsNearbyDuplicate(vector<int> &nums, int k)
  {
    set<int> st;
    int start = 0, end  = 0;

    for(int i=0; i<nums.size(); i++)
    {
      if(st.find(nums[i]) != st.end())
        return true;
      else
      {
        st.insert(nums[i]);
        end++;
      }

      if(end-start > k)
      {
        st.erase(nums[start]);
        start++;
      }
    }

    return false;
  }
};