[Problem Solving with Python] LeetCode 1. Two Sum

質問する

Link: https://leetcode.com/problems/two-sum/
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Test Case Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

に答える

Solution 1.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[j] == target - nums[i]:
                return [i, j]

これは最も考えやすい簡単な解答で、Brute Forceを利用した解答です.nums配列を巡り、各要素にtarget-element値があるかどうかを検索します.
時間複雑性:2次for loop,O(n 2 n^2 n 2)を用いる
スペースの複雑さ:余分なメモリを必要としない->O(1)

Solution 2.

def twoSum_2(self, nums: List[int], target: int) -> List[int]:
    nums_pair = {}
    for i in range(len(nums)):
        nums_pair[target - nums[i]] = i
    for i in range(len(nums)):
        if nums[i] in nums_pair and nums_pair[nums[i]] != i:
            return [i, nums_pair[nums[i]]]

最初のプールは配列をfor loopに繰り返し遍歴するため,時間的複雑さの観点から効率が低い.2回のfor loopのうち1回はインデックスとそれに対応する値を使用するために使用されると考えられる.したがって,配列内の値をインデックスとともに格納する有効な方法を考えるとhashテーブルを用いることが考えられる.ハッシュ・テーブルに値があるかどうかをチェックする場合、O(1)の時間的複雑さが使用されます.これは、配列に値があるかどうかをチェックするよりも効果的です.
第2の解法は,第2の反復サイクルをそれぞれサイクルして解くことである.最初の反復サイクルによりtarget-nums[i]値をインデックスとともにhashテーブルに格納します.2番目の反復サイクルでは、hashテーブルに必要な値があるかどうかを確認します.
Time Complexity: O(2n) -> O(n)
Space Complexity:ハッシュテーブルにアイテム数で格納されるため、正確にはO(n)

Solution 3.

def twoSum_3(self, nums: List[int], target: int) -> List[int]:
    nums_pair = {}
    for i, n in enumerate(nums):
        if n in nums_pair:
            return [nums_pair[n], i]
        nums_pair[target - n] = i

2番目の解では,2回の反復ループがそれぞれループによって解決され,各ループで値の格納と確認がそれぞれ行われると,3番目の解では1回のループで同時に行われることで,この問題をより効果的に解決する.これは、Iterationループを迂回してhashテーブルに値を格納しながら、現在保存されているhashテーブルに必要な値が存在するかどうかを確認する方法です.必要な値が見つかった場合は、すぐに終了して時間を短縮できます.
Time Complexity: O(n)
空間複雑性:最大O(n)

Full Code

Link: https://github.com/datawhales/Python-Code-Notes/blob/main/ps/leet_two-sum_211011.py