Python面试：两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

尽管这是一个看似简单的问题，但是你可以采取多种方法，每种方法都有自己的优点和缺点。

方法一：基本方法

只需遍历所有可能的数字对，然后返回第一对，它们的总和就是你想要的。

这种方法在O(n²)时间和O(1)的空间中运行，其中n是arr的长度。

方法二：优化时间

第二种方法通过使用额外的空间来提高时间复杂度。

首先初始化一个空映射，它将用于存储之前的元素及其索引。

然后，对于列表中的每个元素，首先通过检查sum val-current是否在映射的键集中，来检查之前是否遇到过sum val-current。如果是，那么你已经找到了所需的对，因current_element + (sum_val - current_element) == sum_val 。

否则，将current_element添加到映射中，然后移动到下一个元素。

这种方法在O(n)时间和O(n)空间中运行。在这里，我们只访问每个数组元素一次，因为我们将以前看到的元素及其索引缓存在映射中。

方法三：优化空间

最后一种方法在不使用额外空间的情况下提高了时间复杂度，但是仍然比方法2使用更多的时间。

在这种方法中，我们首先对数组进行排序，并使用排序数组的属性来提高时间复杂度，而不需要使用辅助空间。

为此，我们将使用一个双指针方法。我们在第一个元素处开始一个指针，在最后一个元素处开始第二个指针。然后检查指针所指向的两个元素的和。

如果和太大，则递减第二个指针，如果和太小，则递增第一个指针。

因为数组是排序的，所以我们可以保证数组是不会减少。

这种方法在O(n*log(n))时间和O(1)空间中运行。这里我们假设使用的排序方法在O(n*log(n))时间和O(1)空间中运行，比如堆排序。

请注意，此方法的运行时中的主要因素来自排序操作。之后只进行O(n)比较，因为指针每次移动1，直到它们重叠为止。

在这里，我们改进了基本方法的时间复杂度，而不需要像方法2那样使用额外的存储。我们可以利用数组已排序的事实来最小化我们必须进行的比较的数量。

—End—