LeetCode#1 Two Sums

2017-08-26
#LeetCode #Hash #Python
程式解題/ LeetCode

問題

給定一個整數的陣列nums，其中有兩個數的和會等於目標target，回傳他們的位置，且同個位置不能重複選取。

輸入

nums = [2, 7, 11, 15]
target = 9

輸出

[0, 1]

方法

  • Brute Force
  • Hash Table

第一種方法就是直接使用暴力法，把陣列裡面的元素都加加看，但是時間複雜度會到O(n2)。

1
2
3
4
5
6
class Solution(object):
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

居然吃了一發TLE，沒想到第一題就玩真的，只好另尋他法了。
這時想到python中相當好用的dictionary，第二種方法就是利用雜湊表將讀到的 index 及 value 紀錄下來，即可在讀入一個新的數之後查看這個數的 complement 是否在 table 當中，這樣就可以完美找到一組解啦。
因為使用了dictionary，所以查表的時間只要O(1)，最後時間複雜度降到了O(n)，當然也就順利通過了！

1
2
3
4
5
6
7
8
class Solution(object):
    def twoSum(self, nums, target):
        dic = {}
        for i, n in enumerate(nums):
            if target - n in dic:
                return [dic[target - n], i]
            else:
                dic[n] = i