题目描述
给定一个整数数组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