您现在的位置是:首页 > Javascript
当前栏目
Leetcode题1两数之和 JavaScript语言
2023-04-18 15:27:46 时间
方案一,暴力双循环
读完题目,马上能想到的方案就是双循环,挨个排查,写出来也很快:
var twoSum = function(nums, target) {
const len = nums.length;
for (let i = 0; i < len; i+=1) {
const left = nums[i];
for (let j = i+1; j < len; j+=1) {
const right = nums[j]
if (left + right === target) {
return [i, j]
}
}
}
};
上面方案,最大的问题就是时间复杂度为 O(n^2),所以我们可以想办法在此基础上优化。
方案二,空间换时间(Map)
方案一的思路是,从头到尾挨个去计算数组中任意两个元素的和,然后与给定结果值进行比较,从而找到目标索引,这就导致必须得进行 O(n^2) 复杂度的双循环,效率低下。为了干掉双循环,我们不得不转换思考方式,如何才能在一次迭代中就实现题目要求呢。
题目本质是找到符合要求的两个数组元素的索引,不是非要双循环迭代以此两两配对求和后再比较。既然已经知道目标值,可以采取空间换时间的策略,用一个结构存储遍历过的每个元素和索引,然后我们完全可以仅仅只在一次迭代中,就实现题目要求。具体思路如下:
- 对于当前遍历元素,计算其相对于目标值所需的另一个加数
- 查找存储器是否有这样的加数,如果有,取得此加数的索引,算法结束
- 如果存储结构中找不到这样的加数,则将当前元素及其索引存入存储器,供后续遍历到的元素使用
比如,[2, 7, 11, 15]
目标9
,对于 2
,其需要加数7
,但是现在存储器为空,所以我们将元素2
和其索引0
存入存储器。然后当遍历来到元素7
时,其需要加数2
,查找存储结构发现有2
,取得2
的索引后与7
的索引一同返回,问题即得解。
这里可以发现,对于当前遍历的元素,我们需要存储两个东西:一个东西是数组元素,一个是元素索引;且这两个东西是有关系的,应该两个一组一起存储。另外,我们的存储器必须具有 O(1) 读/写速度,基于以上考虑,我们选择使用 Map
这种类型来做存储器。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const len = nums.length
const map = new Map()
for (let i = 0; i < len; i+=1) {
const currElem = nums[i]
const needNum = target - currElem
if (map.has(needNum)) {
return [map.get(needNum), i]
}
map.set(currElem, i)
}
return []
};
相关文章
- 前端面试 【JavaScript】— typeof 是否能正确判断类型?
- 前端面试 【JavaScript】— instanceof 能否判断基本数据类型?
- 前端面试 【JavaScript】— 能不能手动实现一下 instanceof 的功能?
- 前端面试 【JavaScript】— Object.is和=== 有什么区别?
- 前端面试 【JavaScript】— JS中类型转换有哪几种?
- 前端面试 【JavaScript】— == 和 ===有什么区别?
- 前端面试 【JavaScript】— 对象转原始类型是根据什么流程运行的?
- JavaScript 的 parseInt() 函数
- javascript实现两个数字进行组合
- JS监听键盘按键
- 大前端开发中的路由管理之五:Flutter篇
- Javascript的DOM操作
- 在Vue项目中使用WebSocket技术
- 新手向:前端程序员必学基本技能——调试JS代码
- React 毁了 Web 开发!
- 「JS 逆向百例」cnki 学术翻译 AES 加密分析
- 商标注册域名后缀用什么?商标和域名有哪些区别?
- 网站建设流程是怎样的?需要看重哪些细节?
- 网站域名商标注册流程是什么?网站域名商标有什么用?
- 如何建设一个实用性强的网站 网站上线后如何运营