LeetCode | 001 两数之和
No.001 Two Sum
题目描述
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
分析
首先想到的是两个 for 循环暴力求解，这种做法的时间复杂度为 O(n2)，空间复杂度为 O(1)。
更优的解法是借助哈希表，以空间换时间的思路。在 JavaScript 中，采用对象本身这种键 - 值对的结构作为辅助空间，以减少时间复杂度。
下面的解法具有 O(n) 的时间复杂度，O(n) 的空间复杂度：
JS 实现
var twoSum = function(nums, target) {
var diffMap = {};
for (var i = 0; i < nums.length; i++) {
var cur = nums[i];
var diff = target – cur;
if (diffMap !== undefined) {
return [diffMap, i];
}
diffMap[cur] = i;
}
};
关于
本系列更新 LeetCode JS 版本的思路解法。欢迎一起交流学习。
这是我的公众号：