マイクロソフトの面接問題-整数昇順配列、数M、出力とMの2つの配列要素

質問:昇順でソートされた配列と数値を入力し、配列内で2つの数を検索して、入力された数値とちょうど一致するようにします.
要求時間複雑度はO(n)である.複数対の数字の和が入力に等しい数字Mがあれば、いずれかのペアを出力すればよい.たとえば、配列1、2、4、7、11、15、および数字15を入力します.4+11=15のため、4と11が出力される.
一般的な考え方:
(1)ポインタを配列の頭部と末尾に向けて加算し,Mより小さい場合はヘッドポインタを増やし,より大きい場合は末尾ポインタを小さくする
(2)終了の条件、等しいか頭部=末尾
コードは次のとおりです.

void function（int a[],int n,int M）
{
      int i=0,j=n-1;
　　while(i!=j){
           if(a[i]+a[j]==M){
　　　　　　printf("%d,%d",a[i],a[j]);
                  break;
　　　　}
　　　　a[i]+a[j]>M?j--:i++;
　　}
}

 
普及:
配列中の数が無秩序である場合,O(n)の時間的複雑さの中で,この2つの数をどのように見つけるか.
分析:アルゴリズムについて、筆者から見れば、工事の中で1つの問題の複雑度は3つの部分に分けることができる:時間の複雑度、空間の複雑度、論理の複雑度.この3つのタイプの複雑さのうち、いずれかの複雑さを低減するには、他の2つの複雑さを犠牲にすることによって得ることができる.時間の複雑さと空間の複雑さはみんなよく知られていないと信じて、論理の複雑さは主にコードの論理性と関連するデータ構造を含んで、例えば並べ替えて、線形のデータ構造で実現することができて、木型のデータ構造で実現することができて、木性の構造は線形の構造より論理性が強いため、私達はバランスの二叉木を通じて、赤と黒のツリーは、ある側面をソートする時間の複雑さを低減します.
本題の考え方:
空間的複雑さを犠牲にして時間的複雑さを低減する.犠牲空間の複雑さとは,解を解くのに役立つ情報を保存するためにコンテンツ空間を開くことである.動的計画のように,犠牲空間の複雑さは空間を開いて重なり合うサブ問題の解を保存することである.本題に戻ると,時間複雑度がO(n)であること,すなわち配列要素ごとに1回しか遍歴しないこと,4まで遍歴したときに11が存在するか否かを判定し,2つの数の和を15とするにはどうすればよいか.配列に11という数があるかどうかを保存する必要があります.これが私たちが空間の複雑さを犠牲にして保存するものです.ある数が存在するかどうかを保存するには、ハッシュ・リストを思い浮かべます.次に、時間の複雑さを空間の複雑さで置き換える方法について具体的に説明します.
配列2、1、4、11、7、15、および数字15も入力します.
数字の15から着手して、2つの数の和は15で、共に何組ありますか?0と15,1と14,2と13,...,7と8.15/2+1=8の大きさを定義したHashテーブルTは、ある数の出現回数を統計し、0と15,1と14,2と13,...,7と8をHash関数によって同位置にマッピングする方法を完了する.aがどのようにHash関数によってマッピングされるかのように、最も簡単な方法は、aが15/2=7以下である場合、Hash(a)=aである.aが15/2=7より大きい場合、Hash(a)=15-aとなる.
コードは次のとおりです.

void function（int a[],int n,int M）
{
   int hash[M/2+1]={0};
   for(int i=0,iM/2&&a[i]<=M)
          {
          if(1==hash(a[15-i]))
            printf("%d,%d 
",a[i],a[15-i]);
            }
     }
}