# 轉載請注明出處 http://blog.csdn.net/qq_34175893/article/details/79635054
# 打算開始用python學習算法,并進行一系列的學習過程及心得體會的記錄,歡迎大家持續關注,一起學習。歡迎大家提出意見或建議
# 不關心問題的解決,隻關心不同的解決的問題的思路
在每一個solution前面我都會标明該solution所用時間以及排名,部分優秀的solution還會解析一下思路
# _*_ coding:utf-8 _*_
# 7021ms 2.82%
class Solution0(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
numc = nums
for a,i in enumerate(nums):
for b,j in enumerate(numc):
if i+j == target and a != b:
return [a,b]
# 5068ms 22.43%
class Solution1(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
length=len(nums)
for i in range(0,length):
for j in range(i+1,length):
if nums[i]+nums[j]==target:
return [i,j]
# 1655ms 30.81%
class Solution2(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
#nums.sort() # 不能考慮排序的做法,因為此題要求的必須是原始的index,排序後會失去這個資訊
for first_num in nums:
second_num = target-first_num
index_first = nums.index(first_num)
second_num_start_index = index_first+1
if second_num in nums[second_num_start_index:]:
index_second = nums[second_num_start_index:].index(second_num)
return [index_first,second_num_start_index+index_second]
# 40ms 97.67% #其實說實話,到了這個時間段,程式效率上已經差不了多少了,大家都達到了一個高度,剩下的就是每次運作所帶來的時間誤差,
# 而這時往往1ms的誤差就會相差10%左右的名次
class Solution3(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# 這個思路就比較清奇了,用字典的方式周遊nums的所有值,并依次将每個已周遊過并且沒有在之前的已周遊過的值中找到配對
# 則将其記錄到mydict中,mydict就是用來記錄已經周遊過的值
# 後續的每一個值都是和前面已經周遊過的值進行配對,找到位置
# 相當于是用第二個值去找第一個值
mydict = {} #初始化一個空的字典
indexlist = []
for (index_i, value_i) in enumerate(nums):
value_j = target - value_i
if value_j not in mydict:
mydict[value_i] = index_i
else:
index_j = mydict[value_j]
indexlist.extend([index_j,index_i])
return indexlist #放在這裡更合适,這樣如果有多個結果的話,不會發生錯誤
#return indexlist[::-1] # 如果放在這裡,找到一個結果就會傳回
so = Solution3()
print(so.twoSum([3,2,4],6))