leetcodeブラシノート(一、二数の和)

ずっとleetcodeをブラシしたいと思っていましたが、以前はc言語しかできませんでした.c言語でブラシするのは大変でした.今またコピーを開きました.c++、c++に内蔵されたSTLを勉強した後、leetcodeをブラシするのは簡単でしょう.しかし、いつも自分のアルゴリズムの思考が足りないと感じています.leetcodeをブラシすると自分を向上させることができるでしょう.このテーマは、leetcodeをブラシする過程を記録しています.このテーマを通じて自分にleetcodeを塗って、何か思い出を残したいと思っています.
1.1テーマ
私たちは英語の問題も中国語の問題も来て、ついでに英語を勉強します.
1.1.1 Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

1.1.2両数の和

         nums        target，                      ，          。

                 。  ，                 。

  :

   nums = [2, 7, 11, 15], target = 9

   nums[0] + nums[1] = 2 + 7 = 9
     [0, 1]

ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/two-sum著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
正直に言うと、やはり中国語がわかるように見えますが、英語の問題は試しにしてみましょう.
1.2暴力解法
正直に言うと、テーマを見たばかりで、このような方法を考えるしかありません.大神が思っているほど多くはありません.泡の影響が深いかもしれません.いつも2層のforサイクルを考えて、まずプログラムを書いてみましょう.
1.2.1プログラム

/*
         nums        target，                      ，
          。

                 。  ，                 。

  :

   nums = [2, 7, 11, 15], target = 9

   nums[0] + nums[1] = 2 + 7 = 9
     [0, 1]
*/

#include 
#include 

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> temp;
        //1.     
        int i = 0, j = 0;

        for(i=0; i<nums.size(); i++) {
            for(j=i+1; j<nums.size(); j++) {
                if(nums[i] + nums[j] == target) {
                    cout << "      ，   vector " << endl;
                    cout << nums[i] << "  "<< nums[j] << endl;
                    temp.push_back(i);
                    temp.push_back(j);
                }
            } 
        }
        return temp;
    }
};


int main(int argc, char** argv)
{
    int array[] = {2, 7, 11, 15};
    vector<int> nums(array, array+sizeof(array)/sizeof(int));
    int target = 9;

    Solution p;
    p.twoSum(nums, target);

    return 0;
}

1.2.2解析
暴力解法、論理ははっきりしているはずで、両側forは、配列の中の任意の2つの数を組み合わせて、目標値targetと比較して、等しいならば、説明は成功して、待たないならば、循環を続けます.
1.2.3複雑度分析

時間複雑度:O(n 2)各要素について,配列の残りの部分を巡回することによって対応するターゲット要素を探すことを試み,O(n)の時間を費やす.従って時間複雑度はO(n 2)である.

空間複雑度:O(1).

1.3 2パスハッシュ表
このような実現は私にも分からないで、問題を解く方法を見た後で、やっと大神がすごいことを理解して、意外にも見て、それでは自分で実現して、良い記憶性は腐った筆頭に及ばないで、1回実現するのはいつも見ているより良いです.
1.3.1プログラム

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> temp;

        int i = 0, j = 0;
        //1.     
        #if 0
        for(i=0; i<nums.size(); i++) {
            for(j=i+1; j<nums.size(); j++) {
                if(nums[i] + nums[j] == target) {
                    cout << "      ，   vector " << endl;
                    cout << nums[i] << "  "<< nums[j] << endl;
                    temp.push_back(i);
                    temp.push_back(j);
                }
            } 
        }
        #endif

        //2.       
        //unordered_map  c++    
        unordered_map<int, int> hash_map;

        //      
        for(i=0; i<nums.size(); i++) {
            //hash_map.insert(make_pair(1, 1));
            hash_map.insert(pair<int, int>(nums[i], i));
        }

        //  vector  ，       
        for(i=0; i<nums.size(); i++) {
            cout << target - nums[i] << endl;
            unordered_map<int,int>::const_iterator got = hash_map.find(target - nums[i]);
            if(got != hash_map.end() && i != got->second) { 
            	//            
                cout << i << "  " << got->second << endl;
                temp.push_back(i);
                temp.push_back(got->second);
                return temp;
            }
        }
        return temp;
    }
};

1.3.2解析
これも比較的簡単で、空間から時間を変える思想で、データを取るのが最も速いのはやはりハッシュ表で、ハッシュ表が1つのデータを取る時間がO(1)なため、しかし適切にメモリを増加しました.
全体思想:1回目の遍歴はvectorの値をハッシュテーブルに保存し、2回目の遍歴は、新しいvectorからデータを取り出し、目標値と減算し、この差を利用してハッシュテーブルにデータを取り、もしなければ、説明が一致していない場合、説明が一致した場合.
1.3.3複雑度分析

時間複雑度:O(n)n個の要素を含むリストを2回遍歴した.ハッシュテーブルは検索時間をO(1)に短縮するので,時間複雑度はO(n)である.

空間複雑度:O(n)に必要な余分な空間は、ハッシュテーブルに格納された要素の数に依存し、このテーブルにはn要素が格納されている.

1.4ハッシュ表
1.4.1プログラム

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> temp;

        int i = 0, j = 0;
        //1.     
        #if 0
        for(i=0; i<nums.size(); i++) {
            for(j=i+1; j<nums.size(); j++) {
                if(nums[i] + nums[j] == target) {
                    cout << "      ，   vector " << endl;
                    cout << nums[i] << "  "<< nums[j] << endl;
                    temp.push_back(i);
                    temp.push_back(j);
                }
            } 
        }
        #endif

        //2.       
        #if 0
        //unordered_map  c++    
        unordered_map<int, int> hash_map;

        //      
        for(i=0; i<nums.size(); i++) {
            //hash_map.insert(make_pair(1, 1));
            hash_map.insert(pair<int, int>(nums[i], i));
        }

        //  vector  ，       
        for(i=0; i<nums.size(); i++) {
            cout << target - nums[i] << endl;
            unordered_map<int,int>::const_iterator got = hash_map.find(target - nums[i]);
            if(got != hash_map.end() && i != got->second) {
                cout << i << "  " << got->second << endl;
                temp.push_back(i);
                temp.push_back(got->second);
                return temp;
            }
        }
        #endif 

        //3.      
        unordered_map<int, int> hash_map;

        for(i=0; i<nums.size(); i++) {
            cout << target - nums[i] << endl;
            //              
            unordered_map<int,int>::const_iterator got = hash_map.find(target - nums[i]);
            if(got != hash_map.end()) {
                cout << i << "  " << got->second << endl;
                temp.push_back(i);
                temp.push_back(got->second);
                return temp;
            }

            //    ，        
            hash_map.insert(pair<int, int>(nums[i], i));   
        }

        return temp;
    }
};

1.4.2解析
このハッシュ表は、よく理解できないかもしれませんが、確かに、昨夜一晩考えて、少し納得したようです.まず、例を書きます.配列要素:2、7、4、11、それから第2の中解法に従ってマッチングします.
2 - 2
2 - 7
2 - 4
2 - 11
7 - 2
7 - 7
7 - 4
7 - 11
4 - 2
4 - 7
4 - 4
4 - 11
11 - 2
11 - 7
11 - 4
11 - 11
上の表は、すべてのマッチング状況をリストしています.目の先の友达ではありませんか.対称の関係を見ています.間違いありません.実は、この表は対角線対称です.つまり、少なくとも2つの検索が重複しています.また、2つの下のマークも同じです.削除します.だから、重複を削除します.
2 - 2
2 - 7
2 - 4
2 - 11
7 - 2
7 - 7
7 - 4
7 - 11
4 - 2
4 - 7
4 - 4
4 - 11
11 - 2
11 - 7
11 - 4
11 - 11
このように削除した後、いくつかの不思議な現象を発見したのではないでしょうか.このような表に従って、1回のマッチングを挿入することをサポートします.

は2をハッシュテーブルに挿入し、一致し、一致しなかった.

は、ハッシュ・テーブルに7を挿入し、マッチングする(7−2).

は、4をハッシュ・テーブルに挿入し、マッチングする(4−2、4−7).

は、11をハッシュテーブルに挿入し、その後、一致する(11-2、11-7、11-4)

表の中のものを全部一致させたのではないでしょうか.
1.4.3複雑度分析

時間複雑度:O(n)n個の要素を含むリストを1回だけ巡回した.テーブルでの検索にはO(1)の時間しかかかりません.

空間複雑度:O(n)に必要な余分な空間は、ハッシュ・テーブルに格納されている要素の数に依存し、このテーブルには最大n要素を格納する必要がある.

私もこのような考えが正しいかどうか分かりません.もし間違っていたら、討論を歓迎して、勉強して、一緒に討論します.
テストの結果,要素が同じであることもハッシュテーブルで判断できる.