【数据结构与算法】LeetCode 每日三题

如果你已经对数据结构与算法略知一二，现在正在复习数据结构与算法的一些重点知识
-------------------------------------------------------------------------------------------------------------------------
关注我🌈，每天更新总结文章（多以图文形式，方便记忆，均为网上搜集资料以及AI）⭐
-------------------------------------------------------------------------------------------------------------------------
时间：2025/5/22/ 19: 04分
-----------------------------------
博主链接：黎明smaly-CSDN博客
快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区

---

一、LeetCode 1.两数之和

方法一：

               1.首先我们用最简单的方式，for循环嵌套暴力求解

                  依次判断相加是否等于target目标值

代码：

时间复杂度：

                O(N^2) N是数组中的元素数量，最坏情况下，每个元素都要匹配一次

空间复杂度：

                O(1);

方法二：

            1.采用哈希表的方法 利用unordered_map 

                key存放num[]的值，value 存放此值的下标

             2.遍历到nums[0]的时候判断map中有没有target-num[0]的值

                如果有，代表下标0和下标map->second的值为返回结果

代码：

时间复杂度：

                O(N) N是数组中的元素数量，对于每一个元素，我们可以O(1)的寻找target-num[]

空间复杂度：

                O(N）N是数组中的元素数量，开辟的unordered_map空间

二、LeetCode 49.字母异位词分组

方法一：

            1.字母异位词可以简单理解为：里面的字符都相同，只不过顺序不同

            2.既然知道了定义，我们马上就能发现，我们对每个字符串进行一次排序

               如果排序的结果相同，不就代表他俩属于字母异位词，放在一块即可

            3. 我们要使用哈希unordered_map来存储，key存储排序完的结果，value存放

                 未排序的原字符串,这里注意：value存放的是原字符串集合vector<string>

                 因为unordered_map主键不能重复（能理解吧！）我们value是push_back插入的

代码：

时间复杂度：

                O(Nklogk) N是strs中的字符串数量，k是strs中的字符串的最大长度，因为用到了

                sort,sort的时间复杂度平均为O(nlogn)

空间复杂度：

                O(Nk) N是strs中的字符串数量，k是strs中的字符串的最大长度，需要哈希存储

三、LeetCode 128.最长连续序列

方法一：

              题目中说到了，请设计时间复杂度为O(1)的解法

              所以我们这里还是用哈希

              1.我们使用哈希unordered_set来存储数组中的所有数据

              2.因为我们要求连续序列，所以要去重，才采用的set

              3.我们遍历数组中的所有数据，通过哈希去查找这个数的前面一个数num[]-1

                 是否存在，如果存在，代表他不是连续序列的首元素，跳过他，因为他不是

                 首元素，没有任何意义，最终计算结果长度也不对

               4.我们找到前面一个数不存在的数时，则继续判断下一个数是否存在num[]+1

                   直到不存在为止，将长度保存起来，最终比较大小，找出最长的

代码：

时间复杂度：

                O(N) N是数组的长度

空间复杂度：

                O(N) 需要用哈希存储此数组的数据

---

总结：⭐

这三道题都是跟哈希有关的

如果碰到要求设计时间复杂度为O1的题，首先考虑哈希

对于unordered map / set 的使用要熟悉，哈希离不开这两个STL容器

---

加油，为了更好的明天！

种一棵树最好的机会是十年前，其次是现在