LeetCode 热题 HOT 100
1. 两数之和
1.1 题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
1.2 解答
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
for (var i = 0; i < nums.length; i++) {
for (var j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
var result = new Array();
result[0] = i;
result[1] = j;
return result;
}
}
}
};
-
时间复杂度：O(N^2)，最坏的情况是数组中任意两个数都要匹配一次。
-
空间复杂度：O(1)
-
执行用时：72 ms, 在所有 JavaScript 提交中击败了97.20%的用户
内存消耗：38 MB, 在所有 JavaScript 提交中击败了56.37%的用户
1.3 答案 2
由于暴力搜索的方法是遍历所有的两个数字的组合，然后算其和，这样虽然节省了空间，但是时间复杂度高，一般来说，为了减少时间的复杂度，需要使用空间来换，这里我们想要使用线性的时间复杂度来解决问题，也就是说，只能遍历一个数字，而另外一个数字呢，可以事先将其存储起来，使用一个Map数据结构，来建立数字和坐标之间的映射关系，由于Map是常数级查找效率, 这样在遍历数组的时候, 用target减去遍历到的数字，就是另外一个需要的数字了，直接在Map中查找其是否存在即可，需要注意的是，判断查找的数字不是第一个数字，比如target是4，遍历得到了一个2，那么另外一个2不能是之前的那个2，整个实现步骤为: 先遍历一遍数组，建立Map映射，然后再遍历一遍，开始查找，找到则记录index。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
// 遍历到当前元素的时候, 判断map中是否存在目标值
if (map.has(target - nums[i])) {
// 只循环一遍能够保证 索引不重复
return [i, map.get(target - nums[i])]
}
map.set(nums[i], i)
}
return [];
};
-
时间复杂度: O(N), 其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
-
空间复杂度: O(N), 其中 N 是数组中的元素数量。主要为哈希表的开销。
-
执行用时：76 ms, 在所有 JavaScript 提交中击败了91.99%的用户
内存消耗：38 MB, 在所有 JavaScript 提交中击败了55.75%的用户