1. Two Sum

题目描述

Given an array of integers, return indicts of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

输入与输出

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
    }
};

样例

Given nums = [2, 7, 11, 15], target = 9, because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

题解与分析

解法一（暴力）

该解法依次枚举输入数组中的整数，然后用线性查找方法在余下的数组中寻找是否存在能与之配对的整数。

C++ 代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        // 枚举
        for (auto it = nums.begin(); it != nums.end(); ++it) {
            // 线性查找（find函数定义在"algorithm"头文件中）
            auto pos = find(it + 1, nums.end(), target - *it);
            if (pos != nums.end()) {
                result.push_back(it - nums.begin());
                result.push_back(pos - nums.begin());
                break;
            }
        }
        return result;
    }
};

简单分析可得：该解法的时间复杂度为 O(n^2)。

解法二

O(n^2) 的复杂度并不让人满意，通过观察可以发现上述解法的大部分时间花费在线性查找的过程中。

一个显而易见的优化是使用二分查找算法。二分查找算法需要对数组排序，但是题目要求输出原数组的下标，可以通过额外记录下标数据可以解决该问题。

C++ 代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        using pii = pair<int, int>; // 类型别名（C++11，下同）
        auto func = [](const pii& a, const pii& b) {return a.first < b.first; }; // lambda表达式
        vector<int> result;
        vector<pii> num;
        // 记录下标数据
        for (int i = 0; i < nums.size(); ++i)
            num.push_back(make_pair(nums[i], i));
        // 排序 O(nlogn)
        sort(num.begin(), num.end(), func);
        // 枚举
        for (auto it = num.begin(); it != num.end(); ++it) {
            int key = target - it->first;
            // 二分查找（lower_bound函数定义在"algorithm"头文件中）
            auto pos = lower_bound(it + 1, num.end(), make_pair(key, 0), func);
            if (pos != num.end() && pos->first == key) {
                // 确保下标顺序
                result.push_back(it->second < pos->second ? it->second : pos->second);
                result.push_back(it->second < pos->second ? pos->second : it->second);
                break;
            }
        }
        return result;
    }
};

改进后的时间复杂度为 O(nlogn)。

解法三

解法二的时间复杂度与运行时间已经令人满意，那么能否进一步降低时间复杂度呢？

能。如果使用哈希表，查找的复杂度在理想的情况下可以进一步降低至 O(1) 。由于题目限制，输入中几乎不会存在重复的值（唯一的例外是两个重复值构成答案），我们可以采用 C++ 标准库中的 unordered_map 容器。

C++ 代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        vector<int> result;
        // 枚举
        for (auto it = nums.begin(); it != nums.end(); ++it) {
            int key = target - *it;
            // 查找
            auto keyit = map.find(key);
            if (keyit != map.end()) {
                result.push_back(keyit->second);
                result.push_back(it - nums.begin());
                break;
            }
            map.insert(make_pair(*it, it - nums.begin()));
        }
        return result;
    }
};

理想情况下该解法的时间复杂度为 O(n)。