LeetCodeアルゴリズム-1.Two Sum [easy]

Question:
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].
Solution:
方法1:暴力法:
2つのループを設定し,問題を正面から解決し,2つの数の和を直接判断する.時間複雑度:O(n 2)O(n^2)O(n 2)実行時間:6692 msメモリ消費量:14.2 MB

class Solution:
    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[i] + nums[j] == target):
                    return [i,j]

python関数コメント:パラメータの後にコロンを付けるとパラメータタイプ、関数の後に矢印を付けると戻り値のタイプが表示されます.n u m s:L i s t[i n t]nums:List[int]nums:List[int]はパラメータとそのタイプを表し、末尾の->List[int]はアノテーション関数の戻り値タイプに用いられる.この2つのパラメータタイプは書かなくてもいいので、コメントに属します.関数には三重引用符で書くことができます.
同じように暴力的な解決で、Javaの実行速度はずっと速い.実行時間:210 msメモリ消費量:39.7 MB

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] a = new int[2]; //     
        for(int i = 0; i < nums.length; i++){ //     
            for(int j = i+1;j<nums.length;j++){
                if(nums[i] + nums[j]==target){
                   a = new int[]{i, j};
                }
            }
        }
        return a;
    }
}

方法2:差を探す
2つの数をターゲット値に加算する2つの下付き文字を得る以上、複雑さを低減するために、1つのループだけを使用して、ターゲット値と現在の値の差が配列に存在するかどうかを探し、その差の下付き文字を保存することができます(2つの数はnumsの同じ要素ではありません).時間複雑度:O(n)O(n)O(n)O(n)実行時間:1008 msメモリ消費:14.1 MBクエリーされ、listでindex時間複雑度はO(1)である.Listに内蔵する関数の時間的複雑さ

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            temp = target - nums[i]
            if temp in nums and nums.index(temp) is not i:
                return [i, nums.index(temp)]

以上のコードを簡略化するために,悪い位置を検索する場合,i以降のリストでのみ検索するため,リストをスライスする.発見はnums[:i]で表すほうが便利です.実行時間:972 msメモリ消費量:14.3 MB効果は大きくない

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

方法3:ハッシュ辞書
リスト内のすべての要素とそのindexを対応するdictを確立し、target-numの下付きスケールを直接マッピングすることができ、値の位置を検索するのに時間を費やす必要はありません.実行時間:56 msメモリ消費量:15.5 MB

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        index = {}
        for i, num in enumerate(nums):
            index[num] = i
        for i, num in enumerate(nums):
            j = index.get(target - num)
            if j is not None and j != i:
                return [i,j]

方法2の第2セグメントの方法と同様に、すべての要素をdictに入れてから処理する必要はありません.num 1の前のリストでtarget-num 1が存在するかどうかを探し、存在しない場合はnum 1をdictに入れて、次の検索を行います.存在する場合はnum 2,num 1の位置をそれぞれ出力する.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        index = {}
        for i, num in enumerate(nums):
            if index.get(target - num) is not None:
                return [index.get(target - num),i]
            index[num] = i

驚いた!実行時間:32 ms、すべてのPython 3コミットで98.49%のユーザーメモリ消費量を破った:14.7 MB
最后に书く:言语の文法を熟知するために、アルゴリズムを勉强して、どのようにコードを最适化して、どのように固有の考え方を転换して、だから一歩一歩探求の道を始めます.この問題はLeetCodeの最初の問題で、簡単で、Pythonとその特性を少し復習させてもらいました.