C++面试宝典第11题：两数之和

题目

        给定一个整数数组和一个目标值，请在该数组中找出和为目标值的那两个整数，并返回他们的数组下标，要求时间复杂度为O(n)。可以假设每种输入只会对应一个答案，注意：不能重复利用这个数组中同样的元素。

解析

        这道题主要考察应聘者对算法时间复杂度和空间复杂度的理解，时间复杂度和空间复杂度是衡量算法效率的重要指标。

        时间复杂度是指算法运行所需的时间，通常表示为 O(f(n))。其中n是数据规模，f(n)是算法运行时间的增长函数。时间复杂度反映了算法随着数据规模增长时，运行时间的增长趋势。常见的几种时间复杂度包括：O(1)、O(n)、O(n^2)、O(nlogn) 等。

        空间复杂度是指算法运行所需的额外空间，通常表示为 O(f(n))。其中n是数据规模，f(n)是算法所需额外空间的增长函数。空间复杂度反映了算法在处理大规模数据时，所需额外空间的大小。常见的几种空间复杂度包括：O(1)、O(n)、O(n^2)、O(nlogn) 等。

        对于某些问题，可能存在多种解法，它们的空间复杂度和时间复杂度不同。在实际应用中，我们需要根据问题的规模和资源限制来选择合适的算法，以达到最优的效率。

        回到本题，如果不限制时间复杂度为O(n)，我们可以直接遍历两遍整数数组，示例代码如下。

#include <