链接: https://leetcode.com/problems/two-sum
思路:
建立一个哈希表存放所有数字，迭代访问所有数字， 每次都尝试取出另一个数字的位置，如果成功返回这两个数字位置, 否则将数字的位置存到哈希表。这样能完美解决两个数字相等的情况。时间复杂度和空间复杂度都为o(n). 解决方案基于链接: https://leetcode.com/problems/two-sum/discuss/1610384/Optimal-Solution-Explained
解法:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
prevMap = {}
for i, n in enumerate(nums):
diff = target - n
if diff in prevMap:
return [prevMap[diff], i]
prevMap[n] = i
return []
另外还有一种方法是排序，然后遍历排序后的数字，对另一个数字进行二分搜索。这种方式时间复杂度为o(nlogn), 空间复杂度为o(n)。
class Solution:
def binarySearch(self, nums, lower, uppuer, target):
if lower > uppuer:
return -1
mid = lower + int((uppuer - lower) / 2)
if nums[mid] > target:
return self.binarySearch(nums, lower, mid - 1, target)
if nums[mid] < target:
return self.binarySearch(nums, mid + 1, uppuer, target)
return mid
def twoSum(self, nums: List[int], target: int) -> List[int]:
sorted_numbers = sorted(nums)
len_nums = len(nums)
len_nums_minus_1 = len_nums - 1
for i in range(len_nums):
left = sorted_numbers[i]
right = target - left
index = self.binarySearch(sorted_numbers, i + 1, len_nums_minus_1, right)
if index != -1:
left_index = 0
right_index = 0
j = 0
if left != right:
while j < len_nums:
if nums[j] == left:
left_index = j
if nums[j] == right:
right_index = j
j += 1
return [left_index, right_index]
while j < len_nums:
if nums[j] == left:
left_index = j
j += 1
j = len_nums_minus_1
while j >= 0:
if nums[j] == right:
right_index = j
j -= 1
return [left_index, right_index]
return []
