[LeetCode]1. 两数之和(Two Sum)

题目描述

给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

  • 方法一:排序。将原数组的索引按照数组中数字大小排序,设置两个指针从排序索引数组两端开始向内移动,两数之和等于目标值则返回;
  • 方法二:哈希表。从头开始遍历数组,计算目标值与当前数的差,判断是否在哈希表中,若在,则返回这两个数字,否则将当前数添加到哈希表中。

代码

Python 3.6

方法一:排序

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
sorted_id = sorted(range(len(nums)), key=lambda x:nums[x])
start, end = 0, len(nums) - 1
while start < end:
cur_sum = nums[sorted_id[start]] + nums[sorted_id[end]]
if cur_sum > target:
end -= 1
elif cur_sum < target:
start += 1
else:
return [sorted_id[start], sorted_id[end]]

执行用时 : 56 ms
内存消耗 : 14.2 MB

方法二:哈希表

1
2
3
4
5
6
7
8
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for idx, i in enumerate(nums):
difference = target - i
if difference in hashmap:
return [hashmap[difference], idx]
hashmap[i] = idx

执行用时 : 56 ms
内存消耗 : 14.1 MB

参考

https://leetcode-cn.com/problems/two-sum/comments/9784