算法(leetode,附思维导图 + 全部解法)300题之(1)两数之和

标题:算法(leetode,附思维导图 + 全部解法)300题之(1)两数之和

一 题目描述

两数之和的题目描述

二 解法总览(思维导图)

思维导图

三 全部解法

1 方案1

1)代码:

// 不考虑任何复杂度的限制,2层for循环即可
var twoSum = function(nums, target) {
    let l = nums.length;

    // 因为要找2个数,所以 i值最多为 l-2
    for(let i=0; i<l-1; i++) {
        // 因为要找2个数,所以 j值最多为 l-1
        for(let j=i+1; j<l; j++) {
            // 若 当前2个i、j下标 对应的数值相加 正好等于 target,
            // 直接返回当前的 i、j 所组成的数组(因为题目限定必存在唯一答案)
            let sumTmp = nums[i] + nums[j];
            if(sumTmp === target) {
                return [i, j]
            }
        }
    }
};

2 方案2

1)代码:

// hash法(JS使用 Map数据结构)。“记住,程序 = 数据结构 + 算法”
// 此时,Map是我们的数据结构,具体遍历、判断值等逻辑是我们的算法。
var twoSum = function(nums, target) {
    // 虽然选定了Map结构,但Map是有“key、value”组成
    // 此时我们还需考虑“key、value”的结构(类型值)。
    // 这里 key、value 分别为数组某个具体元素的值、下标
    let l = nums.length,
        m = new Map();

    for(let i=0; i<l; i++) {
        m.set(nums[i], i);
    }

    for(let i=0; i<l-1; i++) {
        let valTmp = target - nums[i],
            idxTmp = m.get(valTmp);
        // 边界:别忘了 2个index 不能相同!(具体为啥大家可以评论区讨论~)
        if(idxTmp !== undefined && i !== idxTmp) {
            return [i, idxTmp];
        }
    }
};

3 方案3(方案2的优化版)

1)代码:

// 优化的核心:遍历次数从2降到1。

// hash法(JS使用 Map数据结构)。“记住,程序 = 数据结构 + 算法”
// 此时,Map是我们的数据结构,具体遍历、判断值等逻辑是我们的算法。
var twoSum = function(nums, target) {
    // 虽然选定了Map结构,但Map是有“key、value”组成
    // 此时我们还需考虑“key、value”的结构(类型值)。
    // 这里 key、value 分别为数组某个具体元素的值、下标
    let l = nums.length,
        m = new Map();

    for(let i=0; i<l; i++) {
        let valTmp = target - nums[i],
            idxTmp = m.get(valTmp);
        // 边界:别忘了 2个index 不能相同!(具体为啥大家可以评论区讨论~)
        if(idxTmp !== undefined && i !== idxTmp) {
            // 不同:因为1遍遍历,所以下标可能需要调整(因为可能i > idxTmp)
            // 但实际上,其实 [1, 2] 和 [2, 1] 都能通过
            return [i, idxTmp];
        }
        // 优化:下面一行代码不放最前面,因为若当前找到了,就不用再 m.set 了
        m.set(nums[i], i);
    }
};
全部评论

相关推荐

一天代码十万三:这都不能算简历吧
点赞 评论 收藏
分享
头像
03-29 15:34
门头沟学院 Java
北斗导航Compass低仿版:能不能先搞清楚优先级啊,怎么可能是项目问题,项目很重要吗?又没学历 又没实习大厂凭啥约面?那玩具项目 没应用在真实生产环境下的 就算做上天又有什么用?早点找个小公司实习 拿小公司实习去投大厂实习,这才是你现在该做的
投递美团等公司7个岗位 简历被挂麻了,求建议
点赞 评论 收藏
分享
其实本来打算等lastday的时候再写的,但是现在提笔写下这篇总结完全是出于自己的想法,今天上午自己被学校发的签到吵醒时才突然想明白了很多事情,遂决定写下本文进行总结,虽然现在顶多算2.5个月,但也大差不差喵。回看这段时间的日常实习,我的关键词是:遗憾,焦虑。当然也有快乐的时候,不过大部分时间都是前面这两种情绪主导。为了避免后人再次踩坑,我将在本文详细解释我遇到的困难&nbsp;+&nbsp;产生的原因&nbsp;+&nbsp;应对的措施。同时总结新人实习时除了业务本身,还有如何处理生活与工作上的平衡,调控自身的情绪,让自己恢复到最好的工作状态。本文不会教你实习怎么去做产出,因为有产出的前提是你的心态足够健康,且在工作之余还有时间去...
wuwuwuoow:你的经历跟挺像,但我实力远没你强,现在只能干外包。但解决焦虑这块我应该比你更有经验,因为我曾经也非常迷茫和焦虑: 1.规律作息。无论节假日,都必须在同一时间点睡觉,同一时间点起床。放假睡的多,工作睡的少,这就是典型的作息不规律。将直接干扰前额叶皮层功能,导致情绪波动(易怒、焦虑)。无论上班还是周末,我都是 11:30 睡,7 点起床。7.5h 睡眠,完全足够了。 2.运动。缓解压力,强身健体,提高免疫力。不要觉得每天没有时间锻炼,都是懒惰的借口。 3.冥想。长期练习会增厚前额叶皮层(理性决策区),缩小杏仁核体积(减少情绪过敏反应,核心),增强情绪调控能力。 方法很简单,任何时候都能做。就是闭上眼睛,只专注自己的呼吸,不去想其他任何事情。你可以尝试一下,你会发现非常难只专注呼吸,会有大量的想法涌现出来(什么走马灯),不要去压抑它们,而是放平心态,把注意力继续放在呼吸上面。 而且最重要的是,冥想让你学会“活在当下”。因为处于冥想的你,除了专注呼吸你还能做什么呢?你什么都做不了。生活也是这样,我们无法改变过去,无法预知未来会发生什么,我们能做的只有手头的事情,除此之外什么都别想,因为你无法去改变它们。 4.工作与生活分离。工作不是生活的全部,生活可不是只有工作。像我放假的时候,从不带电脑回去。放假该玩就玩吧。 上面要是都能做到,其实完全解决不了你工作上的问题,完不成的需求还是完不成,面试该挂还是得挂。不过呢,当你再次迷茫,再次焦虑的时候,你会发现,诶,还好,没这么难受。比如面试挂了,可能以前的你会感觉非常难受。但如果你做到以上 4 点,你还是会难受的,但其实又没这么难受,可能你会这样想:既然挂了我还能怎么样?这公司不要我,有的是公司要我!
投递腾讯等公司6个岗位 >
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务