sum of two numbers
leetcode 1. 两数之和
两数之和
题目描述
方法1
1
2
3
4
双指针
时间复杂度O(nlogn)
空间复杂度O(1)
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
def twoSum(nums, target):
nums = [(v, i) for i, v in enumerate(nums)]
nums.sort()
left, right = 0, len(nums) - 1
while left < right:
if nums[left][0] + nums[right][0] == target:
return [nums[left][1], nums[right][1]]
elif nums[left][0] + nums[right][0] < target:
left += 1
else:
right -= 1
return []
方法2
1
2
3
4
哈希表
时间复杂度O(n)
空间复杂度O(n)
代码如下:
1
2
3
4
5
6
7
def twoSum(nums, target):
hashmap = {}
for i, num in enumerate(nums):
if target - num in hashmap:
return [hashmap[target - num], i]
hashmap[num] = i
return []
本文由作者按照 CC BY 4.0 进行授权