要点:两数之和
描述
给定一个整数数组 nums
和一个整数目标值 target
,请你在该数组中找出 和为目标值 target
的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
1 | 输入:nums = [2,7,11,15], target = 9 |
示例 2:
1 | 输入:nums = [3,2,4], target = 6 |
示例 3:
1 | 输入:nums = [3,3], target = 6 |
提示:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
- 只会存在一个有效答案
**进阶:**你可以想出一个时间复杂度小于 O(n2)
的算法吗?
解题
方法一:暴力解法
1 | var twoSum = function(nums, target) { |
效率
- 55/55 cases passed (100 ms)
- Your runtime beats 50.77 % of javascript submissions
- Your memory usage beats 69.06 % of javascript submissions (38.6 MB)
时间复杂度:$O(N^2)$
空间复杂度:$O(1)$
方法二:Map
1 | /** |
解析
关键点
- 求和转换为求差
- 借助 Map 结构将数组中每个元素及其索引相互对应
- 以空间换时间,将查找时间从 O(N) 降低到 O(1)
ES6对象:Map
Map
是一组键值对的结构,具有极快的查找速度。
1 | var m = new Map([['Michael', 95], ['Bob', 75], ['Tracy', 85]]); |
效率
- 55/55 cases passed (64 ms)
- Your runtime beats 97.8 % of javascript submissions
- Your memory usage beats 36.62 % of javascript submissions (39.9 MB)
时间复杂度:$O(N)$
空间复杂度:$O(N)$
方法三:hash
1 | /** |
效率
- 55/55 cases passed (104 ms)
- Your runtime beats 47.92 % of javascript submissions
- Your memory usage beats 67.84 % of javascript submissions (38.6 MB)
时间复杂度:$O(N)$
空间复杂度:$O(N)$
Tips: Please indicate the source and original author when reprinting or quoting this article.