[LeetCode]1. Two Sum

再エンコードテストの準備
https://leetcode.com/problems/two-sum/5
問題の詳細については、以下のWebサイトを参照してください.

に質問

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.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

方法

問題は、リスト内の2つの数が加算されると、targetとなる2つのインデックス値が返されます.
最初に思いついた方法は,リストの最後の要素を正しい答えが見つかるまで順番に比較するBret−Force法である.
二重for文を使用してすべての状況の数を検索し、条件を満たす場合は返します.O(N2)
第2の方法は、すべての組合せを比較するのではなく、target−num 1によってnum 2を検索することである.O(N)

私が書いたコード

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

💯 他人が解釈するコード

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i,v in enumerate(nums) :
            complement = target - v
            if complement in nums[i+1:] :
                return nums.index(v), nums[i+1:].index(complement) + (i+1)

リストのテストケースに同じ値がある場合は、エラーが発生する可能性があります.
num[i+1:].index(complex)+(i+1)無条件前の部分のインデックスは0であるため,i+1を加える.

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 nums.index(num), nums_map[target - num]

dickShowneryにはindex関数がないため、nums mapはkeynums map[]の値に次のようにアクセスできます.インデックスと値の使用の問題では、列挙が便利です.
比較や閲覧ではなく、正確な答えを一度に見つけることができるディックシーケンスを用いて、クエリはO(1)、全体はO(N)である.
ディクシャナリーの利点は、ハッシュテーブルで実現されるため、最も速い.

🧑🏻 ポスト

問題の核心は、ソートされていないリストで検索することです.
ダブルポインタアルゴリズムを使用しようとしましたが、ダブルポインタはソートされた配列でのみ使用できます.
従って、他の人が説明したように、ディックバッテリを使用すると、第1のルーティング転送方法よりも約100倍性能が向上する.

アルゴリズムの世界は驚くべきようだ.