leetcode-0001 两数之和
题目地址：https://leetcode-cn.com/problems/two-sum/
1.暴力解法
直接双重循环，枚举出所有可能的解，时间复杂度为O(n^2)，空间复杂度为O(1)
var twoSum = function(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j]
}
}
}
}
2.HashTable
- 第一次循环将数组nums中的每个数都放入map中
- 第二次循环判断target – nums[i]是否在map中
时间复杂度O(n), 空间复杂度O(1)
var twoSum = function(nums, target) {
let map = new Map()
for (let i = 0; i < nums.length; i++) {
map.set(nums[i], i)
}
for (let i = 0; i < nums.length; i++) {
if (map.has(target - nums[i]) && i !== map.get(target - nums[i])) {
return [i, map.get(target - nums[i])]
}
}
throw new Error('没有这样两个数')
}
3.HashTable优化版
一次循环，先检查map中是否含有target - nums[i]，如果找到了，那就是我们要的结果；如果没有找到就将这个nums[i]存入map中，继续进行下一次循环，此种解法由于只循环了一次，因此时间复杂度会优于解法2
时间复杂度O(n)，空间复杂度O(n)
var twoSum = function(nums, target) {
let map = new Map();
for (let i = 0; i < nums.length; i++) {
if (map.has(target - nums[i]) && i !== map.get(target - nums[i])) {
return [i, map.get(target - nums[i])]
}
map.set(nums[i], i)
}
throw new Error('没有这样的两个数')
};
更多leetcode题解和数据结构方面的知识，请关注我的github:https://github.com/GuoLizhi/
版权声明：本文为guolizhi原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。