最近再刷leetcode,用python 實(shí)現(xiàn),貼出一些代碼,希望指正.
問題描述:Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
給定一個整數(shù)列表,和一個目標(biāo)數(shù)字,返回列表中和為目標(biāo)數(shù)字的下標(biāo).
樣例輸入:Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
算法思想:
step1 加上索引排序.
step2 用折半查找算法
step3 返回的時候復(fù)原以前的索引.
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
list2 = list(zip([x for x in range(len(nums))], nums))
list3 = sorted(list2, key=lambda x: x[1])
def bin_search(list1, var):
low = 0
hight = len(list1) - 1
while low <= hight:
mid = (low + hight) // 2
if list1[mid][1] == var:
return list1[mid][0]
elif list1[mid][1] > var:
hight = mid - 1
else:
low = mid + 1
return -1
length = len(list3)
for i in range(length-1):
j = bin_search(list3[i+1:],target-list3[i][1])
if j!=-1:
return [list3[i][0],j]
solution = Solution()
nums2 = [3, 2, 3]
print(solution.twoSum(nums2, 6))
