寫在coding前
題目(Easy)
給定一個(gè)整數(shù)數(shù)列该溯，找出其中和為特定值的那兩個(gè)數(shù)凸丸，并返回這符合條件的數(shù)的下標(biāo)广匙。
你可以假設(shè)每個(gè)輸入都只會(huì)有一種答案，同樣的元素不能被重用董栽。
示例：
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
我的解決方案：
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 返回的下標(biāo)列表
rList = []
# 記錄已經(jīng)找到的符合條件的數(shù)值,用來保證：每個(gè)輸入都只會(huì)有一種答案码倦，同樣的元素不能被重用
valueList = []
# 遍歷列表
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
# 如果滿足條件的數(shù)值之前沒有遇到過，則將其下標(biāo)加入列表
if nums[i] not in valueList:
rList.append(i)
if nums[j] not in valueList:
rList.append(j)
valueList.append(nums[i])
valueList.append(nums[j])
return rList
def main():
# 自定義測試用例
rList = Solution().twoSum([2, 7, 11, 15, 3, 2, 18, 6], 9)
print(rList)
if __name__ == '__main__':
main()
以上是我首先能想到的窮舉算法,很明顯這是最基礎(chǔ)的做法,也叫暴力窮舉.算法復(fù)雜度為:
時(shí)間復(fù)雜度為:O(N2)
空間復(fù)雜度為:O(1)
算法進(jìn)化
我們知道對(duì)元素的搜索最快則是O(1)锭碳，即直接索引到袁稽，聯(lián)想只能是Hash表或者是關(guān)鍵字索引。關(guān)鍵字索引（從最小到最大）會(huì)占用額外的內(nèi)存空間工禾。
由于筆者在刷題的過程中順便想練習(xí)一下Python基本語法,所以這里直接采用 Python的dict.
另外我們要求的是元素的索引运提，即Hash表的關(guān)鍵字，所以我們把數(shù)組元素作為dict的key闻葵，而把數(shù)組元素的索引作為dict的value
def twoSum(self, nums, target):
# 相當(dāng)于哈希表
dic = {}
rList = []
valueList = []
# 我們要求的是元素的索引鳄橘，即Hash表的關(guān)鍵字呵哨，所以我們把數(shù)組元素作為dict的key，而把數(shù)組元素的索引作為dict的value
for i in range(len(nums)):
dic[nums[i]] = i
for i in range(len(nums)):
# 防止將同一對(duì)符合條件的值重復(fù)加入
if i not in rList:
# 將符合條件的兩個(gè)元素成為互補(bǔ)元素
# 差值是字典的key且對(duì)應(yīng)互補(bǔ)元素的下標(biāo)不是當(dāng)前元素的下標(biāo)
if (target - nums[i]) in dic.keys() and dic[target - nums[i]] != i:
# 當(dāng)前元素沒有參與過之前的互補(bǔ)配對(duì)
if nums[i] not in valueList:
rList.append(i)
rList.append(dic[target - nums[i]])
valueList.append(nums[i])
return rList
采用哈希表來計(jì)算實(shí)際上是一個(gè)空間換時(shí)間的策略,該算法的算法復(fù)雜度為:
時(shí)間復(fù)雜度為:O(N)
空間復(fù)雜度為:O(N)
他山之石
網(wǎng)上查相關(guān)資料,有 先排序再用二分法 求符合條件的值的方法.但是,這里涉及到排序后原來的索引對(duì)應(yīng)關(guān)系就都變了,這個(gè)時(shí)候找到符合條件的值后還需要找出對(duì)應(yīng)原數(shù)組的索引,因?yàn)轭}目要求返回的是索引!
def twoSum(self, nums, target):
dic = {}
rList = []
valueList = []
# 使用numpy對(duì)數(shù)組進(jìn)行排序
x = np.array(nums)
pynums = np.sort(x)
pyindexs = np.argsort(x)
ahead = len(nums) - 1
behind = 0
# 從有序數(shù)組兩邊向中央逼近
while ahead > behind:
if pynums[ahead] + pynums[behind] == target:
rList.append(pyindexs[behind])
rList.append(pyindexs[ahead])
ahead = ahead - 1
behind = behind + 1
elif pynums[ahead] + pynums[behind] < target:
behind = behind + 1
elif pynums[ahead] + pynums[behind] > target:
ahead = ahead - 1
return rList
這里的時(shí)間復(fù)雜度主要花在了對(duì)數(shù)組排序上,這里直接使用了python里的numpy.
由于python里的numpy可以對(duì)數(shù)組排序并返回排序后原數(shù)組下標(biāo),這樣我們找到符合條件的值就比較容易找到原數(shù)組對(duì)應(yīng)的下標(biāo)了.該方法算法復(fù)雜度為:
時(shí)間復(fù)雜度為:O(NlogN)
空間復(fù)雜度為:O(N)
.
.
.
下一篇:2. 兩數(shù)相加(AddTwoNumbers)
------------------------------20180308夜
刷Leetcode，
在我看來次舌，
其實(shí)是為了維持一種編程狀態(tài)馒稍！
