LeetCode第一題：兩數(shù)之和
Ps：本系列文章只為記錄自己刷LeetCode過程中的解題過程和思路垂睬。
題目描述： 給定一個整數(shù)數(shù)組 nums和一個目標值 target谐腰，請你在該數(shù)組中找出和為目標值的那兩個整數(shù)错敢，并返回他們的數(shù)組下標。
你可以假設每種輸入只會對應一個答案该溯。但是认轨，數(shù)組中同一個元素不能使用兩遍绅络。
示例： 給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解題過程和思路： 當我瀏覽了一便這個題目的時候，心里想嘁字，哇恩急，通俗易懂，這不是超簡單的嘛纪蜒。emmm衷恭，題目意思是懂了，那么怎么用計算機解呢纯续？首先映入我腦海中的是：emm随珠，最基礎的解法吧——暴力， 把數(shù)組所有可能的兩數(shù)之和都求出來不就好了猬错，但是這樣子的做法時間復雜度是O(n^2)窗看， emmm，實在不可取倦炒。接著显沈，我又想呀想呀，怎么降低時間復雜度呢逢唤？ 排序怎么樣拉讯？排序了之后從小到大遍歷數(shù)組，算出每個數(shù)與后續(xù)數(shù)的和鳖藕，由于排序過了魔慷，計算出來的求和結(jié)果將會是一個遞增的序列，當求和結(jié)果大于目標值 target 之后便停止計算吊奢，接著遍歷數(shù)組中第二個數(shù)盖彭。咦，好像可行页滚，可以避免一些無用的求和計算。由于用了排序铺呵，因此時間復雜度在O(nlogn)與O(n^2)之間裹驰。博主太笨了，之后再想了許久也沒想到更優(yōu)的解法片挂，因此參考了LeetCode上的大佬們的題解幻林，哇贞盯，第一次感到世界如此奇妙』龋可以通過建立哈希表躏敢，也就是字典的方式來加快查詢速度（空間換時間），具體怎么做呢整葡？件余。將數(shù)組的值作為key，索引作為value建立字典遭居，這樣子如果我們對于數(shù)組中某個數(shù)num啼器，要查找是否存在另外一個數(shù)another_num，使得兩數(shù)之和為target俱萍，那怎么查找 another_num 這個數(shù)比較快呢端壳？ 通過我們前面建立的字典，可以通過判斷字典的keys里是否有another來查找枪蘑，因此查找一般只需要O(1)時間（當沒出現(xiàn)沖突的時候）损谦。
解題收獲： 字典的妙用——以空間換時間的方式加快查找效率，記好啦岳颇。
代碼展示：
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
nums_d = {}
for index,num in enumerate(nums): # 遍歷nums數(shù)組枚舉兩個數(shù)中的第一個數(shù)
another_num = target-num # 目標-第一個數(shù)求第二個數(shù)
if another_num in nums_d: # 遍歷nums_d字典判斷兩個數(shù)中的第二個數(shù)是否存在
return min(index, nums_d[another_num]), max(index, nums_d[another_num]) # 若存在則返回
else:
nums_d[num] = index # 以num為兩個數(shù)中的第一個數(shù)找不到答案照捡，就將其放入存放第二個數(shù)的字典
結(jié)果展示：
