【C算法打怪专栏】LeetCode 1. 两数之和哈希表解法总结一、 题目链接LeetCode 官方网址LeetCode 1. 两数之和二、 核心思路与优化暴力解法的局限如果用两层循环去遍历所有组合时间复杂度会达到O ( N 2 ) O(N^2)O(N2)数据量大时会超时。哈希表优化一趟哈希边遍历数组边将元素及其下标存入unordered_map键存数值值存下标。在存入之前先检查哈希表中是否存在target - nums[i]即我们需要的另一个数。核心优势时间复杂度直接降至O ( N ) O(N)O(N)且由于是“先查找后插入”完美避免了把“元素自身”重复利用的问题。三、 C 标准精简源码#includevector#includeunordered_mapusingnamespacestd;classSolution{public:vectorinttwoSum(vectorintnums,inttarget){unordered_mapint,intmp;// 键数值值对应下标for(inti0;inums.size();i){intnum2target-nums[i];// 如果在哈希表中找到了另一半直接返回各自的下标if(mp.find(num2)!mp.end()){return{mp[num2],i};}// 没找到就把当前元素存入哈希表mp[nums[i]]i;}return{};// 题目保证有解防警告兜底}};四、 复杂度分析时间复杂度O ( N ) O(N)O(N)其中N NN是数组的长度。我们只对数组进行了一次单循环哈希表的查找和插入平均时间复杂度均为O ( 1 ) O(1)O(1)。空间复杂度O ( N ) O(N)O(N)最坏情况下如答案在最后两个数或无解前需要把所有元素存入哈希表中。