2つの合計問題- LeetCode

2つの合計
整数numsと整数ターゲットの配列が与えられた場合、2つの数値を返します.

最初の変種(1つの解決だけを仮定します)

セットアップ
質問を読む-私たちは基本的に数字の配列とターゲット番号を与えられている.
ターゲットの中に2つを見つけ、それを配列として返します.
これはA + BをA + Bのように見つけるために沸騰します.

アルゴリズム
これを行う一つの方法は、以下のような答えを得るまで、数をループして追加することです

public int[] TwoSum(int[] nums, int target) {

        for(int aCounter=0;aCounter<nums.Length-1;aCounter++)
        {
            for(int bCounter=aCounter+1;bCounter<nums.Length;bCounter++)
            {
                if(nums[aCounter]+nums[bCounter] == target)
                    return new int[] {nums[aCounter],nums[bCounter]}; // Early Termination
            }
        }
    }

次のように配列とターゲットを想像してください

int [] nums =[2,1,5,8,6]
target = 14

これは、我々の結果が最後の2つの数

nums[3]+nums[4] = 14 (target)

上記のアルゴリズムは

aCounter = 0 // First Iteration
2 + 1 = 3
2 + 5 = 7
2 + 8 = 10
2 + 6 = 8
Total loops done = 4
aCounter = 1 // Second Iteration
1 + 5 = 6
1 + 8 = 9
1 + 6 = 7
Total loops done = 7 // Third Iteration
aCounter = 2
5 + 8 = 13
5 + 6 = 11
Total loops done = 9
aCounter = 3 //Fourth Iteration
8 + 6 = 14

ご存知のように、10回の繰り返しで答えが見つかりました.基本的には、ループB(n - 1 - a)回を実行している最悪の場合、答えを得ることができました.したがって、最悪の場合は、カウンターと同様にBcounterに依存します.複雑な数学の脇-ループ内にループがあるので、これはO(acounter * bcounter)時間複雑さアルゴリズムです.私たちはAcounterとBcounterが同じであるということを知っています.値を格納していないので、余分なスペースを必要としません.
しかし、nums配列が大きいならば、上記の解決は非些細なランタイムを持つでしょう.それがサイズ1010と最後の2つの数字が一致するとき、この配列を想像してください.
空間複雑性を犠牲にして時間複雑性を最適化できるか?私が一度だけ配列を越える方法がありますか?

a + b = target 

手段

 a = target - b

それで、私が過去の値をルックアップする方法を持っていて、上記の公式を使用するならば、私はこれが条件を満たすかどうか決定することができます
私の処分のデータ構造を通して、どのようなデータ構造が高速ルックアップを行うのでしょうか?ハッシュベースのデータ構造EG :ハッシュセット、辞書など.
我々が配列を通過するとき、我々はハッシュ値に値を格納する方法については、新しい値に達するたびに、我々は上記の式が満たされているかどうかを確認します.

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
       HashSet<int> hash=  new HashSet<int>();
       for(int i =0;i<nums.Length;i++)
        {
            if(hash.Contains(target-nums[i]))
                return new int[]{target-nums[i], nums[i]};
            else
                hash.Add(nums[i]);
        }
        // If guaranteed a solution, will never hit
        return new int[0];
    }
}

これは配列を一度だけ実行しなければなりません.
ハッシュ
ターゲット
B
タルク
{ }
14
2
12
{ 2 }
14
1
13
{ 2 }
14
5
9
｛2,1,5｝｝
14
8
6
｛2,1,5,8｝
14
6
8
Target - Bは8を探し、ハッシュは8を持ち、プログラムは終了します.
複雑な数学を脇に-私たちは一度ループ時間の複雑さはO(n)ですが、我々はリソースとして今使用しているものは時間を節約するためのスペースです.私たちは、Nを通してループを通してN - 1の要素を保存しています-これは基本的にO(n)空間の複雑さです.

コモンミス

読みやすい変数-あなたが気がつくならば、私はコードの第2の部分の間、私はコードの最初の部分でacounterを使いました.理解の容易さの違いは、2つの間で簡単に見ることができます.

                   return new int[]{target-nums[i], nums[i]};

                return new int[] {nums[aCounter],nums[bCounter]};

エラー処理-コードのハンドルのどれもnull numsまたは空のnumsです.我々は常に入力をsanitizeする必要があります.

   if(nums == null)
               return new int[0];

初期終了-問題が1つの解決策があるところでは、我々はその情報を使用して早く終了するべきです.基本的に、答えが長い配列の最初の部分にあるならば、我々は計算を浪費していません.これは一般的にビッグO(最悪の場合)で記述されるアルゴリズムの時間複雑性に影響を与えないことを覚えておいてください.

隠された条件とエッジの場合-エッジの場合は、アルゴリズムを処理するためのセットを持っている.負の数、ゼロターゲット等

その他

は、目標

にマッチするすべての可能な組合せを返します
a .早めに終了しない

は、一致した組合せ

のインデックスを返します
a .ハッシュセットの代わりに辞書を使う