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)
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
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言語版はまた今後時間がある時に補足します。
Author And Source
この問題について(LeetCode No.1 TwoSum), 我々は、より多くの情報をここで見つけました https://qiita.com/qingheihei/items/b77bc4d023addcf4004a著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .