我们先来看题目给定一个整数数组nums和一个整数目标值target请你在该数组中找出和为目标值target的那两个整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。你可以按任意顺序返回答案。示例 1输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums[1] 9 返回 [0, 1] 。示例 2输入nums [3,2,4], target 6 输出[1,2]示例 3输入nums [3,3], target 6 输出[0,1]提示2 nums.length 104-109 nums[i] 109-109 target 109只会存在一个有效答案进阶你可以想出一个时间复杂度小于O(n2)的算法吗先来分析基础要求中会传入一个整型数组 nums、一个目标值 target 作为参数返回值同样是一个装有我们找到的 i 和 j 两个索引的整型数组并且题目假定了 nums 数组中两数之和为 target 的情况有且仅有一种。最简单的方法就是两层嵌套循环进行枚举即#include vector using namespace std; class Solution { public: vectorint twosum(vectorint nums, int target) { int n nums.size(); for(int i0;in;i) { for(int j 0;jn;j) { if(nums[i]nums[j] target) {return {i,j};} } } return{}; } };我们来解释一下这个程序类 Solution 中有一个公有函数 twosum()它会返回一个 int 类型的变长数组 vector即为我们所要的两个下标构成的数组其参数为我们传入的整型数组 nums以及我们的目标值 target。首先我们用一个整型变量 n 来记录传入的数组长度以便循环时确定循环终点接下来就是常见的双重循环随后内层循环每一次会判断当前的两数之和是否为我们所要的 target若是则返回此时的 {i,j}否则继续循环若循环结束后仍找不到则直接返回空数组。本程序的实质就是外层循环遍历到一个元素利用target-nums[i]算出一个need然后内层循环再线性查找这个need。需要注意到的是函数中传递的数组参数并不是数组本身而是它的引用这就避免了每次调用时需要传入整个数组的巨大性能开销。此时显而易见我们的程序的时间复杂度为而空间复杂度为。接下来我们考虑题目中的额外要求即进一步压缩程序的时间复杂度我们重新审视整个程序进行过程我们遍历到nums[i]时我们想知道的是在已经遍历过的元素中有没有一个元素与此时此刻的nums[i]相加能够等于target若有我们就直接返回但上面的双重循环遍历中内层循环每次都在执行繁琐的线性查找它不会记录曾经遍历过的元素。整个程序就是在外层执行枚举时间复杂度为在内层执行线性查找时间复杂度同样为。故而我们就能想到如果能让另一个容器实时存储我们遍历过的每一个元素在我们遍历到数组中某个元素时它需要的另一个数一定是target-nums[i]只要从记录下的遍历过的元素中找到这个元素那么就能直接返回下标将原本内部循环的时间复杂度压缩到总体时间复杂度被压缩到。而只有两种方式可以实现的查找即为直接寻址与哈希表如果用直接寻址我们就需要开辟一个相当大的数组来存储考虑到题目中的范围我们不采用这种方式。转而考虑哈希表。对于哈希表它能够接收任意类型的 key经过哈希函数处理后将其装入哈希桶中返回一个哈希桶数组的下标。在没有冲突时哈希查找的时间复杂度直接为即使有冲突也可以通过链地址法和开放寻址法将平均查找长度压缩到。这样一来我们的目标就很明确了每次遍历到数组中的某个元素时先计算当前元素与target的差值need将need作为key传入哈希函数计算出桶下标然后在该桶内与need进行比对查找若查找到则直接返回下标组若没有则执行一次哈希插入将当前的值与下标作为一个键值对通过哈希函数计算添入哈希桶数组内。写成程序即为#include vector #include unordered_map using namespace std; class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int seen; // 数值 - 下标 for (int i 0; i (int)nums.size(); i) { int need target - nums[i]; // 先查找之前是否出现过 need auto it seen.find(need); if (it ! seen.end()) { return {it-second, i}; } // 没找到则把当前元素和下标存入哈希表 seen[nums[i]] i; } return {}; } };在函数中首先创建了一个哈希表seen存储元素值和下标随后开始遍历数组元素在每一步计算出need随后执行seen.find(need)该函数会对传入的need进行哈希函数运算找到对应的桶下标以后再在桶内寻找最终返回一个指向桶中节点的迭代器iterator接下来是判断对于find()函数如果找到了末尾都没有找到需要的那个元素那么返回的迭代器就会指向end()此时通过我们存储的it迭代器来与end()进行对比如果不相等那么说明哈希查找没有执行到末尾成功找到了我们需要的need元素那么直接返回it-second也就是need元素对应的下标否则就是没有找到那么我们此时将元素和下标存入哈希表中再遍历下一个元素。这样一来外层枚举的时间复杂度为内层计算need查找need插入元素的时间复杂度都为整体时间复杂度为。在过程中有几个需要注意的语法知识1. 外层枚举时需要将 nums.size() 的返回值显式转换为 int 类型否则编译器会有 Warning。因为 nums.size() 的返回值是 size_t即无符号整数而我们遍历用的数值类型是 int故而存在一定隐患。2.对于存储seen.find(need)返回的变量类型其原本是一个指向对应哈希表的迭代器即unordered_mapint,int::iterator我们采用auto来让编译器自动识别。3.最后在未找到情况下插入当前元素时采用了oprator[]方式来插入seen[nums[i]] i就是向哈希表中插入{nums[i],i}的键值对这是大多数情况如果里面已经有了这个元素那么就会进行覆盖。总结来说原本的方法用两层循环解决外层枚举内层执行线性查找总时间复杂度为优化后的方法将内层的线性查找修改为哈希表插入与查找将查找的平均时间复杂度压缩到整体复杂度被压缩到.
