Leetcode 1. Two Sum

給出一個array返回兩個數字的索引使雙方加起來等於目標值

想法

1.暴力解 （不推荐）

直接兩次遍歷,找尋是否兩數相加為目標值。

程式碼：

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

2.hash table解

講解:
先創建一個字典結構,使用for in 遍歷,當遇到目標減當前值的數值存在字典裡時,return答案,否則將字典加入一筆資料key為當前數字value為當前索引儲存。

程式碼：

def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_dict = {}
        for i in range(len(nums)):
            if(target-nums[i] in nums_dict):
                return [i,nums_dict[target-nums[i]]]
            else:
                nums_dict[nums[i]] = i