Leetcode100-两数之和

news/2024/10/30 18:19:21/

参见官方题解

一、学到的知识

  1. 正面寻找两个数之和相加等于某个数,如 a+b = c,不如反过来寻找 a = c - b

    正面寻找需要两层 for 循环,把每个数都进行遍历,所以时间复杂度较高

    反过来则可以通过维护一个 a 的集合,每次通过查询 c - b 是否在集合中,判断是否存在 a = c - b

    存在,则返回答案;不存在,则将 a 插入集合中, 待下次查询

  2. 想一下,我们为什么把 a 插入集合中,而不是 c - b呢?

    如果把 c - b 插入集合,意味着我们将判断 a 是否在集合中,总之就是要判断是否存在 a = c - b,两者写法其实都可以

二、代码

  1. 版本1
    时间复杂度 O(N)
    空间复杂度 O(1)

    比较好想到的一个方法是先使用一层 for 循环枚举 a,再使用一层 for 循环枚举 b,判断 a + b == c 是否为真即可
    而且也容易想到一点优化,对于位于 x 位置的元素,1…x-1次循环的时候,nums[x]已经被匹配过,所以无需再匹配,所以在代码中,可以看到,第二层枚举 b 的循环,从 i + 1 开始

    class Solution
    {
    public:vector<int> twoSum(vector<int>& nums, int target){const int Size = nums.size();for (int i = 0; i < Size; ++i){for (int j = i + 1; j < Size; ++j){if (nums[i] + nums[j] == target){return {i, j};}}}return {0, 0};}
    };
    
  2. 版本2
    时间复杂度 O(NlogN)
    空间复杂度 O(N)

    这是版本1的优化, 前文提过,需要寻找 a + b = c,我们可以把 b 移至右侧,寻找 a = c - b,我们很自然的想到,可以维护一个数的集合,再从中寻找元素是否存在

    而这个集合的查找的复杂度,就决定了我们算法的复杂度,在代码中,我们使用了标准库中的 map,它的查找效率是 LogN

    class Solution
    {
    public:std::vector<int> twoSum(std::vector<int>& nums, int target){const int size = nums.size();map<int, int> Map;for (int i = 0; i < size; ++i){const int gap = target - nums[i];auto iterator = Map.find(gap);if (iterator != Map.end()){return {iterator->second, i};}Map.insert({nums[i], i});}return {-1, -1};}
    };
    

http://www.ppmy.cn/news/28235.html

相关文章

文件的打开关闭和顺序读写

目录 一、文件的打开与关闭 &#xff08;一&#xff09;文件指针 &#xff08;二&#xff09; 文件的打开和关闭 二、文件的顺序读写 &#xff08;一&#xff09;fputc 1. 介绍 2. 举例 &#xff08;二&#xff09;fgetc 1. 介绍 2. 举例1 3. 举例2 &#xff08;三&…

【蓝桥杯每日一题】双指针算法

&#x1f34e; 博客主页&#xff1a;&#x1f319;披星戴月的贾维斯 &#x1f34e; 欢迎关注&#xff1a;&#x1f44d;点赞&#x1f343;收藏&#x1f525;留言 &#x1f347;系列专栏&#xff1a;&#x1f319; 蓝桥杯 &#x1f319;我与杀戮之中绽放&#xff0c;亦如黎明的花…

线材-电子线载流能力

今天来讲的是关于电子线的一个小知识&#xff0c;可能只做板子的工程师遇到此方面的问题会比较少&#xff0c;做整机的工程师则必然会遇到此方面问题&#xff0c;那就是线材问题。 下面主要说下电子线的过电流能力。&#xff08;文末有工具下载&#xff09;电子线&#xff08;h…

聚类算法(上):8个常见的无监督聚类方法介绍和比较

无监督聚类方法的评价指标必须依赖于数据和聚类结果的内在属性&#xff0c;例如聚类的紧凑性和分离性&#xff0c;与外部知识的一致性&#xff0c;以及同一算法不同运行结果的稳定性。 本文将全面概述Scikit-Learn库中用于的聚类技术以及各种评估方法。 本文将分为2个部分&…

urho3d的自定义文件格式

Urho3D尽可能使用现有文件格式&#xff0c;仅在绝对必要时才定义自定义文件格式。当前使用的自定义文件格式有&#xff1a; 二进制模型格式&#xff08;.mdl&#xff09; Model geometry and vertex morph data byte[4] Identifier "UMDL" or "UMD2" …

【软件测试面试题】大厂头条:如何定位bug?实际案例拿offer还不简单......

目录&#xff1a;导读前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09;前言 问题&#xff1a; 用…

详讲函数.2.

目录 5. 函数的嵌套调用和链式访问 5.1 嵌套调用 5.2 链式访问 小结&#xff1a; 6. 函数的声明和定义 6.1 函数的声明&#xff1a; 6.2 函数的定义&#xff1a; 5. 函数的嵌套调用和链式访问 函数和函数之间可以根据实际的需求进行组合的&#xff0c;也就是互相调用的…

【java基础】包装类,自动装箱和自动拆箱

文章目录基本介绍包装类自动装箱自动拆箱包装类注意事项包装类比较包装器内容不可变基本介绍 有时&#xff0c;需要将int这样的基本类型转换为对象。所有的基本类型都有一个与之对应的类。 例如&#xff0c;Integer类对应基本类型int。通常&#xff0c;这些类称为包装器&#…