LeetCode No.1 TwoSum

就活に向けて、LeetCodeでアルゴリズムを勉強しようと思います。
これから毎日LeetCodeのProblemを解題し記録します。

まず Top 100 Liked Questions から始めたいと思います。
順番としては、Easy -> Medium -> Hardとなります。

では、本日のTaskはNo.1 TwoSumです。
参考：leetcode twosum

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].

解答1
時間計算量：O(n)
空間計算量：O(n)

python3code

    def twoSum(self, nums: List[int], target: int):
        i = 0
        while i < len(nums):
            if i == len(nums)-1:
                return "no result"
            wanted = target - nums[i]
            rest = nums[i+1:]
            if wanted in rest:
                return [i, rest.index(wanted)+i+1]
            i = i+1

pythonのlist型の特性を利用し、list[i+1:]の中でtarget-nums[i]を探します。
またlist.index()を使うのも便利ですね。
結果は下記となります。

解答2

python3code

    def twoSum(self, nums: List[int], target: int):
        i = 0
        dict = {}
        while i < len(nums):
            if nums[i] in dict:
                return [dict[nums[i]], i]
            else:
                dict[target-nums[i]] = i
            i = i+1

pythonの辞書型を利用します。空間計算量が少し増えますが、実行時間がより速くなります。
結果は下記となります。

以上です。C言語版はまた今後時間がある時に補足します。