[LeetCode] 1. Two Sum - Python

Algorithm Problem with Python — 32day

問題の説明📖

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.
せいげんじょうけん

2 <= nums.length <= 103

109 <= nums[i] <= 109

109 <= target <= 109

Only one valid answer exists.

I/O例
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

問題を理解する🔑

リストとターゲットリストでターゲットを作成できる2つの数値インデックスを返します.
問題自体は簡単ですが、いくつかの最適化方法があるので、どのように最適化できるかを確認する必要があります.

首都コード▼▼

これは、ターゲットから最初の数字を減算すると、すぐに2番目の数字がわかるからです.

の列挙によりindex、valueを取得し、キーと値をディックシーケンスに置き換えます.

ターゲットから最初の数値を減算した結果、鍵がクエリされます.

ターゲットの最初の数字(容易にはaと呼ぶ)がディックシーケンスに存在し、最初の数字のインデックスがディックシーケンスキーaの値ではない場合、最初の値のインデックスとディックシーケンスキーaの値が返される.

コード作成

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        # 키와 값을 바꿔서 딕셔너리로 저장
        for i, num in enumerate(nums):
            nums_map[num] = i
            
        # 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
        for i, num in enumerate(nums):
            if target - num in nums_map and i != nums_map[target - num]:
                return [i, nums_map[target - num]]

整理する😄

問題自体は本当に簡単です
この問題の最適化を学習する前に、「加速」で計算します.
ダブルfor文を用いてすべての組合せO(n)を1つずつチェックする²)の時間的複雑さを表します.
この問題では,ターゲットから1番目の数字を減算することで2番目の数字の利点を識別し,2番目の数字をキーとして既存のインデックスを値に変換し,O(n)の時間的複雑さを低減できる.
LeetCodeは実行時間が52ミリ秒であることを発見した.
LeetCode運転結果

以前は問題を解決できるかどうかしか考えていなかったが,成功した結果ではなくアルゴリズムの解に集中した.
これからは心を落ち着けて一つ一つの問題を練習しよう
Reference

朴尚吉、『Pythonアルゴリズムインタビュー』、書満(2020)、p 169-175.