企业官网建设流程全解析

我们先来看题目

给定一个整数数组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: vector<int> twosum(vector<int>& nums, int target) { int n = nums.size(); for(int i=0;i<n;i++) { for(int j =0;j<n;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: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, 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_map<int,int>::iterator，我们采用auto，来让编译器自动识别。

3.最后在未找到情况下插入当前元素时，采用了oprator[]方式来插入，seen[nums[i]] = i，就是向哈希表中插入{nums[i],i}的键值对，这是大多数情况，如果里面已经有了这个元素，那么就会进行覆盖。

总结来说，原本的方法用两层循环解决，外层枚举，内层执行线性查找，总时间复杂度为；优化后的方法，将内层的线性查找修改为哈希表插入与查找，将查找的平均时间复杂度压缩到，整体复杂度被压缩到.