二つの合計

今日、私は人気のLeetCode質問2つの合計に3つの解決に出かけるつもりです.
問題はこれです:数字の数と目標番号を与えられて、目標番号に加える2つの数字のインデックスを返してください.
解決方法

O ( N ^ 2 )時間、O ( 1 )スペース
二つのループを使用して配列をループし、ターゲット番号に追加する2つの数値のインデックスを見つけることができます.

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]

O ( n )時間、O ( N )スペース
ハッシュテーブルを使用して数値をキーとしてインデックスとして格納します.それから、我々は違い(目標番号)がハッシュ表にあるかどうかチェックします.もしあれば、数値のインデックスと差分のインデックスを返します.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        values = {}
        for i, num in enumerate(nums):
            diff = target - num
            if diff in values:
                return [i, values[diff]]
            values[num] = i
        return []

O ( nlogn )時間、o ( 1 )スペース
つのポインターメソッドを使用できます.配列をソートし、数値とそのインデックスの配列を作成した後、I = 0とJ = len ( array )- 1の2つのポインタiとjを作成します.合計が目標より小さい場合、インクリメントIは大きい場合、インクリメントJが等しい場合、インデックスを返します.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        i = 0
        j = len(nums) - 1
        sortedNums = sorted(zip(nums, range(len(nums))))
        while i < j:
            if sortedNums[i][0] + sortedNums[j][0] == target:
                return [sortedNums[i][1], sortedNums[j][1]]
            elif sortedNums[i][0] + sortedNums[j][0] < target:
                i += 1
            elif sortedNums[i][0] + sortedNums[j][0] > target:
                j -= 1