LeetCodeアルゴリズムの2数の和Java詳細解(第1題)

LeetCodeアルゴリズムの2数の和Java詳細解(第1題)
タイトル要件:整数配列numsとターゲット値targetを指定し、その配列の中でターゲット値の2つの整数を見つけて、それらの配列の下に返してください.入力ごとに1つの答えしか対応しないと仮定できます.ただし、配列内の同じ要素は2回使用できません.例:nums=[2,7,11,15]が与えられ、target=9はnums[0]+nums[1]=2+7=9であるため[0,1]を返す
以上は力ボタンの中の原話で、要求は実は少し巻いて、実はあなたに配列があることを教えて、今すでに配列の中の2つの数の和を知っていて、あなたにどの2つの数を探し出して、そして配列の下標に戻ります.
暴力解法:考え方:1番目の数を順番に後ろのすべての数に加算し、2番目の数と後ろのすべての数を順番に加算して...結果を見つけるまで.外層サイクル、配列の最初の数値を保存し、その後、内層サイクル、2番目の数から順に遍歴し、2番目の数に1番目の数を加え、targetに等しいかどうか、3番目の数に1番目の値を加えるかどうか...外層の1ラウンド目のサイクルが終わった後、1番目の数を排除することができ、その後、外層サイクルは2番目の数から、内層は3番目の数から...

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

最適解法:最適解法の鍵は,HashMapにおけるkeyがハッシュで実現され,ハッシュの検索時間がO(1)であることにあるが,HashSetもハッシュで実現されているのに,なぜSetを用いないのか.それは,この問題が最後に出力するのは配列下標であるため,配列下標を保存しなければならないからである.したがって、mapのkeyで各遍歴した数値を保存し、valueで配列の下付き文字を保存します.アルゴリズムフロー:Mapを初期化します.このときMapは空で、最初の配列値を順次巡回し、targerで最初の数を減算し、減算した結果をint aで一時保存します.このときmapに値aのkeyが存在するか否かを判断するが、もちろん、初めては肯定的に存在しないので、この場合は最初の配列値と配列下標を保存する(ここではaではなく被減数を保存することに注意).次に、次の順にaを算出し、mapにaのkeyが存在する場合、検索は終了する.(ここでは、前のkeyに保存されているのは被減数であり、aは減算された結果であり、keyにおける被減数と後のある数の減算された結果とが同じである場合、この減算は実際に繰り返されているが、被減数と結果が位置を変えただけであることを説明する.例として、10−3=7であり、このとき3は被減数であり、10−7=3であり、このとき3は結果であるため、3+7=10が見つかった)

class Solution {
    public int[] twoSum(int[] nums, int target) {
            HashMap<Integer,Integer> map = new HashMap<>();
            for(int i=0;i<nums.length;i++){	
                int a = target-nums[i];
                if(map.containsKey(a)){
                    return new int[]{map.get(a),i};
                }else{
                    map.put(nums[i],i); 
                }
            }
            return null;
         }
    }