面接問題01.02.両数の和

面接問題01.02.両数の和
前言:主な目的は、出力を継続し、アルゴリズム問題を分かりやすく、さまざまな方法で解析し、アルゴリズム能力を高めることです.回答者のレベルも限られていて、みんなで進歩しています.
面接問題01.02.両数の和
タイトル:
整数配列numsと整数目標値targetを指定します.この配列で、目標値の2つの整数を見つけて、それらの配列の下付きを返します.入力ごとに1つの答えしか対応しないと仮定できます.しかし,配列内の同じ要素は答えに繰り返されない.任意の順序で答えを返すことができます.
例1:

  ：nums = [2,7,11,15], target = 9
  ：[0,1]

例2:

  ：nums = [3,2,4], target = 6
  ：[1,2]

最も簡単な方法は、暴力の二重循環です.
1.ダブルサイクル加算判定

var twoSum = function(nums, target) {
    let fist = 0;
    for(let i=0;i

実行時間:84 ms、すべてのJavaScriptコミットで65%のユーザーメモリ消費量を破った:37.9 MB、すべてのJavaScriptコミットで69%のユーザーを破った
解析:私たちはまずテーマを分析して、配列の中で重複しない2つの加算とある数を望んで、最初に考えた方法はすべての項目を加算して、正しい答えが得られるまで.だから、私たちはまず循環循環配列の各項目を書いて、それからfirstを得て、firstは私たちの中の1つで、それではどのように別の項目を見つけますか?firstの値を取得した後、firstを自身以外の各項目に加算し、結果をtargetと比較し、最終結果が見つかるまでサイクルを行う.
2.最適化方案一

var twoSum = function(nums, target) {
    // a,b,c,d 
    // ab,ac,ad
    // ba,bc,bd
    // ca,cb,cd,
    // da,db,dc,
    for(let i=0;i

実行時間:84 ms、すべてのJavaScriptコミットで66%のユーザーメモリ消費量を破った:37.7 MB、すべてのJavaScriptコミットで96%のユーザーを破った
解析:このスキームは私が1の解析を書く時に思いついたスキームで、1の暴力的な解読に対する最適化バージョンとして、私がコードに書いた注釈を見ることができて、実は解法1の中で多くの繰り返し計算のステップがあります.私たちが2回目のサイクルでは、最初のパラメータの後ろのビットから、繰り返しのサイクルを除去することができますが、実行時間とメモリは、最初の方法とあまり差はありません.の不服です...(PS:やはり、人材を分かち合うことが最大の受益者であり、皆さんも多く分かち合うことを望んでいます.)
3.キャッシュ検索の残りの半分

var twoSum = function(nums, target) {
    let obj = {};
    for(let i=0;i

実行時間:84 ms、すべてのJavaScriptコミットで65%のユーザーメモリ消費量を破った:37.9 MB、すべてのJavaScriptコミットで60.71%のユーザーを破った
解析:このスキームは依然として解法1と解法2の最適化版として使用することができ、最も際立ったハイライトは1つのループしか使用していないが、主に他のデータ構造を利用しており、本質は依然として2つのループが検索されているだけである.オブジェクトを使用して配列の各項目を格納し、値は下付き、keyは各項目の値とします.このような設定の目的は、主にオブジェクト[属性名]で直接値を見つけることができることです.この解法で注意しなければならないのは、jsでは0を偽物と見なし、正しい結果に0が含まれている下付きは切り落とされることです.だからif判断の時にundefinedと比較するように変更しました.
まとめ
実はこの3つの方案の構想と本質はすべて類似して、主な違いは最適化、最適化、引き続き最適化です.私达はふだんコードを书く时実はこのような考えが必要で、需要を完成すればいいのではなくて、自分の书いたすべての行のコードに直面して1つ闻いて、この行のコードは削除することができますか?私たちのプログラムで実行されているすべてのコードが自分の役割を果たすことを望んでいます.
絵を貼ってください.実はこの問題はもう何度もやっています.よく新しいことをしています.