[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

方法二:哈希表

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash_map;
int lens = nums.size();
for (int i = 0; i < lens; ++i) {
auto it = hash_map.find(target - nums[i]);
if (it != hash_map.end()) {
return {it->second, i};
}
hash_map.emplace(nums[i], i);
}
return {};
}
};

执行用时 : 12 ms
内存消耗 : 10.5 MB

Python 3.6

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