描述

有一个整数数组，在数组里找两个数字，使得这两个数字的和为指定的值。

写一个函数，返回这两个数字的索引，返回的索引index1一定要小于index2，索引值不要基于零。

可以假设数组里只有一个答案。

分析

在一个数组里找两个数字的和等于指定值，最直观的方法是把数组中的每一个数字和这个数字之后的每一个数字相加，以此判断是否等于指定值，伪码如下：

for i=0 -> n-1:
    for j=i+1 -> n:
    if (A[i] + A[j] == target)
        find the target value

这种方法的时间复杂度为O( $n^2$ )，空间复杂度为O(1)。

有没有可能降低时间复杂度呢？可以借助辅助空间来降低时间复杂度的，使用一个哈希表，当遍历到一个数字时，计算出其和目标值得差值，然后在哈希表里查找是否有这个数字，有的话则查找成功，如果没有，则把当前数字放入到哈希表，继续遍历。

代码实现如下：

void findTwoSum01(int A[], int n, int target, int &index1, int &index2)
{
    index2 = index1 = -1;
    std::unordered_map<int, int> cache;
    for(int i=0; i<n; i++) {
        int reduce = target - A[i];
        auto iter = cache.find(reduce);
        if (iter != cache.end()) {
            index1 = (std::min(i, iter->second)) + 1;
            index2 = (std::max(i, iter->second)) + 1;
            break;
        }
        
        cache[A[i]] = i;
    }
}

这种方式的时间复杂度和空间复杂度都是O(n)，典型的借助空间降低时间复杂度的做法。

代码在这儿