LeetCode / Two Sum

（ブログ記事からの転載）

19/7/7時点でLeetCodeの第一問目に掲載されている問題ですが、シンプルでいてなかなか歯ごたえのある良問。

[https://leetcode.com/problems/two-sum/]

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

リスト中の2つの異なる要素を足してターゲットの値となる要素のインデックスを求めろ、という問題です。

回答・解説

解法1

まず、THE 力技。

class Solution:
    def twoSum(self, nums, target):
        for i, n1 in enumerate(nums):
            if target - n1 in nums:
                for j, n2 in enumerate(nums):
                    if i != j and n1 + n2 == target:
                        return [i,j]
                        break
        return []

これは分かりやすいですね。単純にループを回していくだけです。

ただ、時間計算量が$O(n^2)$になるのが難点。これを改良したのが次の解法。

解法2

class Solution:
    def twoSum(self, nums, target):
        d = {}
        for i,n in enumerate(nums):
            d[n] = i
        for i,n in enumerate(nums):
            tmp = target - nums[i]
            if tmp in d.keys() and d[tmp] != i:
                return [i,d[tmp]]
        return []

辞書（ハッシュテーブル）を用意し、一端各要素の値とインデックスをkey:valueとして格納しておいた後、targetと各要素の値を引いた値がkeyとして存在するか、参照していきます。

これだと時間計算量は$O(n)$になります。ただ今度は空間計算量も$O(n)$に増してしまうのが難点ではあります。

より簡潔に次のように書くこともできます。

解法3

class Solution:
    def twoSum(self, nums, target):
        d = {}
        for i,n in enumerate(nums):
            tmp = target - nums[i]
            if tmp in d.keys():
                return [i,d[tmp]]
            d[nums[i]] = i
        return []