LeetCode 第 1 号问题:两数之和

本贴最后更新于 1789 天前,其中的信息可能已经斗转星移

LeetCode 第 1 号问题:两数之和

本文首发于公众号「五分钟学算法」,是图解 LeetCode 系列文章之一。

个人网站:https://www.cxyxiaowu.com

题目来源于 LeetCode 上第 1 号问题:两数之和。题目难度为 Easy,目前通过率为 45.8% 。

题目描述

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题目解析

使用查找表来解决该问题。

设置一个 map 容器 record 用来记录元素的值与索引,然后遍历数组 nums。

  • 每次遍历时使用临时变量 complement 用来保存目标值与当前值的差值
  • 在此次遍历中查找 record ,查看是否有与 complement 一致的值,如果查找成功则返回查找值的索引值与当前变量的值 i
  • 如果未找到,则在 record 保存该元素与索引值 i

动画描述

视频讲解

代码实现

// 1. Two Sum
// https://leetcode.com/problems/two-sum/description/
// 时间复杂度:O(n)
// 空间复杂度:O(n)
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> record;
        for(int i = 0 ; i < nums.size() ; i ++){
       
            int complement = target - nums[i];
            if(record.find(complement) != record.end()){
                int res[] = {i, record[complement]};
                return vector<int>(res, res + 2);
            }

            record[nums[i]] = i;
        }
    }
};

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • someone

    小吴师兄还录了视频啊
    但是在手机上看这个视频是马赛克画质(捂脸)

  • someone
    作者

    手机上无法调整分辨率么,建议在 B 站上观看,别忘了投币弹幕一波~

  • someone

    小吴师兄 B 站号多少呀?我去关注一波 ~

  • someone
    作者
  • someone

    小吴师兄没有 java 版本的么?

    1 回复
  • someone
    作者

    后面大部分代码都是 java 的,之前是 c 的,不过基本上都差不多

  • MisterBooo

    后面的内容大部分代码都是 java 版的了

请输入回帖内容 ...