LeetCode 热题 100——day1两数之和

✨ 把代码写进星轨用逻辑丈量宇宙。导航链接个人主页 星轨初途基础语言专栏 C语言 、 数据结构C 进阶专栏 C学习竞赛类 、⚙️ C专栏开发类刷题实战专栏 算法及编程题分享 、 力扣每日刷题分享文章目录两数之和题目链接方法一暴力枚举复杂度分析代码实现方法二哈希表复杂度分析代码实现方法三排序 双指针复杂度分析代码实现总结两数之和题目链接LeetCode两数之和方法一暴力枚举最直接的思路是使用两层循环枚举数组中所有不同的下标组合(i, j)。对于每一组下标判断nums[i]nums[j]target如果条件成立就返回这两个元素的下标。这种方法不需要额外的数据结构代码比较容易理解但当数组长度较大时执行效率较低。复杂度分析时间复杂度O(N^2)需要枚举所有可能的下标组合空间复杂度O(1)只使用了少量额外变量。代码实现classSolution{public:vectorinttwoSum(vectorintnums,inttarget){intnnums.size();intl-1,r-1;for(inti0;in;i){for(intji1;jn;j){if(nums[i]nums[j]target){li,rj;break;}}}return{l,r};}};方法二哈希表对于当前元素nums[i]我们需要寻找的另一个数为target-nums[i]我原本还想使用数组记录每个数是否出现但题目中的数值范围比较大并且还可能出现负数直接开数组会造成大量空间浪费。因此可以使用哈希表保存已经遍历过的元素及其下标数值-下标遍历数组时先检查哈希表中是否已经存在target - nums[i]如果存在说明已经找到了答案如果不存在就将当前元素和下标存入哈希表。需要注意必须先查找再插入当前元素避免同一个元素被使用两次。复杂度分析时间复杂度O(N)每个元素只需要进行一次哈希表查找和插入空间复杂度O(N)最坏情况下需要将所有元素存入哈希表。代码实现classSolution{public:vectorinttwoSum(vectorintnums,inttarget){unordered_mapint,intcnt;intl-1,r-1;for(inti0;inums.size();i){if(cnt[target-nums[i]]){li,rcnt[target-nums[i]]-1;}cnt[nums[i]]i1;//以免查找时cnt[target-nums[i]]0无法判断是没有还是下标为0}return{l,r};}};也使用find()判断目标值是否存在可以避免operator[]在查找时自动向哈希表中插入新的键值对。方法三排序 双指针原数组是无序的因此不能直接使用双指针。我们可以先将每个元素的数值和它在原数组中的下标绑定在一起pair数值,原下标然后按照数值从小到大排序。排序完成后设置两个指针l指向当前最小的元素r指向当前最大的元素。计算num[l].firstnum[r].first根据计算结果移动指针如果两数之和大于target说明当前和太大需要让右指针左移如果两数之和小于target说明当前和太小需要让左指针右移如果两数之和等于target返回两个元素在原数组中的下标。因为排序会改变元素原来的位置所以必须额外保存每个元素的原下标。复杂度分析时间复杂度O(NlogN)主要开销来自排序空间复杂度O(N)需要额外保存元素数值及其原下标。代码实现classSolution{public:vectorinttwoSum(vectorintnums,inttarget){// first 保存元素值second 保存元素原下标vectorpairint,intnum(nums.size());for(inti0;inums.size();i){num[i].firstnums[i];num[i].secondi;}// pair 默认优先按照 first 从小到大排序sort(num.begin(),num.end());intl0;intrnum.size()-1;while(lr){intsumnum[l].firstnum[r].first;if(sumtarget){// 当前和太大右指针左移--r;}elseif(sumtarget){// 当前和太小左指针右移l;}else{// 返回两个元素在原数组中的下标return{num[l].second,num[r].second};}}return{};}};这种方法通过排序将问题转换成了有序数组中的双指针查找。总结方法核心思路时间复杂度空间复杂度暴力枚举使用两层循环枚举所有下标组合判断两数之和是否等于targetO(N^2)O(1)哈希表遍历数组时使用哈希表查找target - nums[i]是否已经出现O(N)O(N)排序 双指针保存元素原下标并排序然后使用左右双指针逐渐逼近目标值O(NlogN)O(N)三种方法各有特点暴力枚举思路最直接也是最好想到哈希表时间复杂度最低排序 双指针能够帮助我们理解双指针算法的使用前提和移动规律。在实际刷题时可以先写出暴力解法再根据题目数据范围考虑使用哈希表或双指针进行优化。