アルゴリズム:二数の和(two-sum).

整数配列numsとターゲット値targetを指定します.この配列でターゲット値の2つの整数を見つけて、その配列の下付きを返します.
入力ごとに1つの答えしか対応しないと仮定できます.ただし、配列内の同じ要素は2回使用できません.
例
与えられたnums=[2,7,11,15],target=9
nums[0]+nums[1]=2+7=9なので[0,1]を返します
方法1:暴力法
暴力法は簡単で、各要素xを遍歴し、target-xに等しい値のターゲット要素が存在するかどうかを検索します.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

複雑度分析

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

空間複雑度:O(1).

方法2:2パスハッシュテーブル
実行時間の複雑さを最適化するには、配列にターゲット要素が存在するかどうかを確認するより効果的な方法が必要です.存在する場合は、インデックスを見つける必要があります.配列内の各要素とそのインデックスを互いに対応させる最善の方法は何ですか?ハッシュ表.
空間交換速度により,探索時間をO(n)からO(1)に低減できた.ハッシュ・テーブルは、この目的のために構築され、ほぼ一定の時間で迅速な検索をサポートします.衝突が発生すると,ルックアップ時にO(n)に劣化する可能性があるため,「近似」で記述した.しかし、ハッシュ関数を慎重に選択すれば、ハッシュテーブルで検索する際にO(1)に償却されるべきである.
単純な実装では2回の反復が用いられた.最初の反復では、各要素の値とインデックスをテーブルに追加します.次に、2回目の反復では、各要素に対応するターゲット要素(target-nums[i])がテーブルに存在するかどうかを確認します.ターゲット要素はnums[i]そのものではないことに注意してください.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

複雑度分析

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

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

方法3:一次ハッシュテーブル
事実は私たちが一度に完成できることを証明している.反復して要素をテーブルに挿入すると、テーブルに現在の要素に対応するターゲット要素がすでに存在するかどうかを確認します.もしそれが存在するならば、私たちはすでに対応する解を見つけて、すぐにそれを返します.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

複雑度分析

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

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