從今天起在此紀錄用python寫leetcode的心路歷程
希望能以一天兩三題的速率下去更新
讓自己的程式更加精進

題目:

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.

簡單來說就是題目給定一個目標值(target)和一個list,而我們找出list中兩個相加等於target的數的index,再以陣列型態回傳

一開始看到這題我的想法相當直觀:

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

直接暴力遍歷尋找相加等於target的兩個值,想當然耳,最後速度只有5776ms(faster than 13.38%)(沒超時就該偷笑了)

於是我找了一下更快的寫法,在討論區發現了叫hash map的方法
研究過後程式變這樣

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

先建立一個dictionary,用以紀錄 value:index 的hash map
從第一項開始,透過target減去當下值尋找對應值是否在hash map內
若無則在hash map 寫入 當下值:當下index,再跑下一項
直到在hash map找到對應值的存在,就將對應值index取出和當下index一同return

透過邊遍歷檢索邊建立hash map大幅加快了程式的運行,複雜度由O(n^2)降到O(n),運行速度也增為52ms (faster than 99.64%)
同時在研究過程中學到hash(雜湊)的概念

本題學習到的重點:雜湊(hash)
那我們下題見