[LeetCode] 1 Two Sum

以前「ビッグデータ構造」を初めて学び、ネット上でLeetCodeのテストを見て、問題を塗り始めました.第1題はランキング1位です.
Given an array of integers, find two numbers such that they add up to a specific target number.The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2
これが二つのサイクルじゃないかと思った.
順調に提出した後、実行タイムアウトを発見し、プログラムの入力が超大きな配列であることをよく見て、tag:Array、Hash Tableを見た.
ネット上で3つのアイデアを見つけました
考え方1:各要素について、target、時間複雑度O(n^2)という別の要素を探して、これも私が最初に使った方法です.

loop1 i=0 to size-2

    loop2 j=i+1 to size-1

        if(vs[i]+vs[j]=target)  

 i+1,j+1

考え方2:まずソートし、最初と最後の2つのポインタを真ん中に寄せ、2つのポインタが指す要素はtargetより大きく、最後のポインタを移動し、targetより小さく、結果が見つかるか、2つのポインタが出会うまで移動します.時間複雑度O(nlogn).この方法は値3 Sum,4 Sumなどを広めることができる.

sort(vs[])

loop i=0,i=size-1;i!=j;;

    if vs[i]+vs[j]>target

        j--;

    if vs[i]+vs[j]<target

        i++;

    else

         ， 

構想3:hashmapを利用して、各要素の値をkeyとして、配列インデックスをvalueとしてhashmapに格納して、それから配列要素を遍歴して、hashmapの中でそれとtargetの要素を探します.時間複雑度O(n),空間複雑度O(n).ただしhash_を使用するmapでは実現できませんが、mapに赤黒樹を適用するとhash_より時間効率が低いと思います.mapですが、相変わらず高いです.

 1 vector<int> twoSum(vector<int> vs, int target)

 2 {

 3     map<int,int> hm;

 4     vector<int> result;

 5     vector<int>::size_type i,j;

 6     for(i=0;i!=vs.size();i++)

 7         hm.insert(pair<int,int>(vs[i],i));

 8     for(i=0;i!=vs.size();i++)

 9     {

10         map<int,int>::iterator iter=hm.find(target-vs[i]);

11         if(iter!=hm.end()&&iter->second!=i)// 

12         {

13             j=iter->second;

14             if(i<j)

15             {

16                 result.push_back(i+1);

17                 result.push_back(j+1);

18             }

19             else{

20                 result.push_back(j+1);

21                 result.push_back(i+1);

22             }

23         }

24     }

25     return result;

26 }

ps:初めてこの問題をして、2日かけて完成して記録しました.