🔎 アルゴリズム-2つのLetcodeと(2つのsum)java

📌 質問する

n個の整数配列が与えられた場合、ターゲット値を満たす2つの要素のインデックスを、配列内の2つの要素の和で求める.
(時間複雑度O(N)制限)

📌 に答える

時間的複雑さはO(N)に限られるため、2つの要素のすべての組合せを2つのfor文で表示することは不可能である.
Mapを使用してfor文を展開した.

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

Mapに格納されたキー値格納先配列からiを減算した値
入力した要素がMapのキー値と同じ場合、この2つの要素の和はtargetです.
(Mapのキー値から対応するインデックスの2番目の値が減算されているため)