言語はPython3でやってます。

問題

https://leetcode.com/problems/two-sum/description/

①いくつかの数字からなる配列と、②1つの数字が渡される。 ①の中の2つを足し合わせると②の数字となる組み合わせが1組だけあるので、その組み合わせを見つける問題。 なお、値を2つ返すのではなく、①におけるインデックスを返す必要がある

解答①

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        minus_nums = []
        loop_count = 0
        while nums:
            v = nums.pop(0)
            if len(minus_nums) >= 1 and v in minus_nums:
                return [loop_count, minus_nums.index(v)]
            minus_nums.append(target - v)
            loop_count += 1

最初に思いついたのはこれ。①の配列から1個ずつ数字を取り出し、② - 取り出した数値を別の配列に格納していく。 ①の配列から取り出した数値が、値を格納した配列の中にあればOK。 その時点でのループ回数と、別の配列でヒットした位置のインデックスを返す。

ある程度問題なく動作はするが、計算量がO(n^2)となってしまう。

メジャーな解答

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_map = {}
        for i, num in enumerate(nums):
            complement = target - num
            if complement in num_map:
                return [num_map[complement], i]
            num_map[num] = i

①の配列から一つずつ数値を参照するのは一緒で、② - 取り出した数値を別の場所に格納するのも一緒。ただ、ハッシュマップ(dict)に key→引き算した数値、value→そのインデックスを格納することで、数値がヒットするかのチェックする部分(complement in num_map)が平均時間計算量O(1)となる。

ハッシュマップと配列の計算量の違いは意識できてなかったので、勉強になった。