これはLeetCodeと他のキュレート解決説明(インデックス)のシリーズの一部です.
あなたがこの解決が好きであるか、それが役に立つとわかるならば、このポストを好きにしてください.

Leetcode Problem #1 (Easy): Two Sum

2 .合計

整数numsと整数ターゲットの配列が与えられた場合、2つの数値のインデックスを返します.
それぞれの入力が1つの解決策を持っていると仮定することができます.
任意の順序で答えを返すことができます.

例1 :

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

例2 :

Input: nums = [3,2,4], target = 6
Output: [1,2]

例3 :

Input: nums = [3,3], target = 6
Output: [0,1]

制約

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

前もって

つのループの解決策も考慮する価値があるものに時間を無駄にしないでください!ランタイム242479142
また、解決策は、この合計を得るために必要な値のインデックスを返す必要があることを理解する必要がありますので、左または右に移動する入力を並べ替えることはできません.
だから、別の方法を考えることができます!

解決策

複数の解決策がありますが、1つのアプローチでO(n)ランタイムの複雑さを与えることができます.とHashMapのを使用している!
それではどのように動作しますか?
配列からすべての数値のインデックスをマップとして格納し、HashMapのキーとなりインデックスが値になるようにします.
どのように役立つのだろうか?

だけで再び配列をループし、必要な2番目の番号を見つけ、それがHashMapに存在するかどうかをチェックします!
見つかった場合は、インデックスを見つけて、最初の数と2番目の数のインデックスを返します.

この解決策は、本当にエレガントで、本当によく働きます、唯一の欠点は、同様にO(n^2)のスペース複雑さを必要とするということです.

実装

いくつかの問題に対してPythonは本当に簡潔な解決策を提供します

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dictionary = {}

        for index, value in enumerate(nums):
            dictionary[value] = index


        for i in range(len(nums)):
            second_number = target - nums[i]
            if second_number in dictionary.keys():
                second_index = nums.index(second_number)

                if i != second_index:
                    return sorted([i, second_index])

The result

注意-インタビュアーはあなたに尋ねるかもしれません、なぜあなたは1の代わりに2つのループを作成しましたか?
ジャワの

int[] twoSum(int[] nums, int target) {

        final Map<Integer, Integer> map = IntStream.range(0, nums.length)
                .boxed()
                .collect(Collectors.toMap(i -> nums[i],
                        i -> i,
                        (a, b) -> b));

        for (int i = 0; i < nums.length; i++) {
            int secondNumber = target - nums[i];

            if (map.containsKey(secondNumber)) {
                int secondNumberIndex = map.get(secondNumber);

                if (secondNumberIndex != i) {
                    return new int[]{i, secondNumberIndex};
                }
            }

        }

        return new int[]{};
    }