[leetcode]Contains Duplicate III

   leetcode      ，   C++ map       。

に言及

    Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

1つの配列numsを与えて、2つの異なる数(下付きはそれぞれi、j)が存在するかどうかを判断し、それらは以下の2つの条件を満たす.

| i - j | <= k

| nums[i] - nums[j] | <= t

考え方1:二層遍歴(暴力法)
この考え方は比較的簡単で、leetcodeのこの問題もこのような方法を採用することはできないと思います.やはり、次のコードを提出するとタイムアウトになります.

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        bool res = false;
        int ns = nums.size();

        for(int i = 0; i < ns - 1; i++)
        {
            //int max = 0;
            for(int j = i + 1; j < ns && j <= i + k; j++)
            {
                long result = nums[i] - nums[j];
                if(result > INT_MAX || result <= INT_MIN) return false;

                if(abs(nums[i] - nums[j]) <= t)
                {
                    return true;
                }
            }   

        }
        return res;
    }
};

考え方2:Binary Search Treeを利用して、無意味な検索を削減する
この考え方は,C++におけるmapデータ構造の特性を利用してnumsデータ中の(nums[i] - t, nums[i] + t)の範囲内の数を探索し,その下付き文字が条件1を満たすか否かを判断する.コードに合わせて見てみましょう.

class Solution {
private:
    bool overflow(int one, int two)//           
    {
        long res = one - two; 
        if(res > INT_MAX || res <= INT_MIN) return true;
        else return false;
    }
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if(t < 0) return false;
        if(k < 1) return false;

        bool res = false;
        int ns = nums.size();
        map<int, int> hmap; // map
        for(int i = 0; i < ns; i++)
        {
            //int max = 0;
            map<int, int>::iterator it = hmap.find(nums[i]);

            if(it != hmap.end()) //   i    nums[i]    
            {
                if(abs(it->second - i) <= k) return true; //             。
                it->second = i; //        1，            。       ，it  ，              。 i   nums   i  。

            }
            else
            {
                hmap[nums[i]] = i; //     ，   
            }

            //     map      ， nums[i]  （    ）        。    (nums[i] - t, nums[i] + t) 。
            map<int, int>::iterator temp_it = hmap.find(nums[i]);

            if(temp_it != hmap.begin()) // it begin  ，      。
            {
                temp_it--;

                while(temp_it != hmap.begin())
                {
                    if(overflow(temp_it->first, nums[i])) return false;
                    if(abs(temp_it->first - nums[i]) > t) break; //     2   ，    

                    if(abs(temp_it->second - i) <= k) return true;

                    temp_it--;
                }

                       begin  
                if(temp_it == hmap.begin())
                {
                    if(overflow(temp_it->first, nums[i])) return false;
                    if(abs(temp_it->first - nums[i]) <= t)
                    {
                        if(abs(temp_it->second - i) <= k) return true;
                    }
                }
            }


            //  nums[i] + t    。
            temp_it = hmap.find(nums[i]);
            temp_it++;
            while(temp_it != hmap.end())
            {
                if(overflow(temp_it->first, nums[i])) return false;
                if(abs(temp_it->first - nums[i]) > t) break;

                if(abs(temp_it->second - i) <= k) return true;

                temp_it++;
            }
        }
        return res;
    }
};

まとめ
この問題を通じてmapの以下のいくつかの特性をまとめることができます.

mapのストレージ構造は、検索ツリーと見なすことができる.

mapの反復器の自己加算自己減算は、二叉木を中順序で遍歴する過程であり、その実現方式は双方向中順序チェーンテーブルであるべきである.

mapのキー値の検索の平均時間複雑度はlogレベルである.