LeetCode算法-两数之和

最近业余时间相对比较充分，决定闲下来的时候上LeetCode撸一撸算法题，正好把自己的C++知识也补一补。很有意思的事，发现LeetCode上给出的官方题解都是Java版本的，难道C++已经被彻底抛弃了吗？不过这样也好，正好给自己用C++解题留下了充足的空间。今天主要看一下LeetCode的第一题，后续会不断推进。

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

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

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法一：
拿到题目很容易想到的解法，就是使用暴力法，直接对每个元素进行遍历，找到满足要求的目标元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i=0; i<nums.size(); i++) {
            for (int j=i+1; j<nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    return vector<int> {i, j};
                }
            }
        }
        return vector<int>();
    }
};

复杂度分析：
时间复杂度：O(n2)。LeetCode执行用时204ms。
空间复杂度：O(1)。Leetcode内存消耗9.4MB。

解法二：
很明显二次遍历的时间复杂度太高，可以考虑进行优化。题目的核心是要找到目标元素并返回其索引，而哈希表是一种能够保持数组中每个元素与其索引相对应的最好方法，通过以空间换取时间，我们可以以O(1)的时间复杂度来查找元素。以哈希表解决本题的基本思路是，首先通过一次遍历，将元素和索引以键值对放入哈希表；然后第二次遍历，检查满足要求的元素是否存在于表中。LeetCode官方解题使用Java中的Map来实现哈希表，在C++中，我们考虑使用STL中的unordered_map。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> m;
        for (int i=0; i<nums.size(); i++) {
            m.insert(std::make_pair(nums[i], i));
        }

        for (int i=0; i<nums.size(); i++) {
            int complement = target - nums[i];
            if (m.find(complement) != m.end() && m.find(complement)->second != i) {
                return vector<int> {i, m.find(complement)->second};
            }
        }
        return vector<int>();
    }
};

复杂度分析：
时间复杂度：O(n)。LeetCode执行用时32ms。
空间复杂度：O(n)。LeetCode内存消耗10.8MB。

这里关于C++ STL中的哈希表unordered_map主要有两个知识点：
1、查找某个元素x是否存在于表的键中：比较 m.find(x) 与 m.end()是否相等，相等则不存在，不相等则存在；
2、取出表中某个键对应的元素：m.find(x)->second。

解法三：
解法二中的两次遍历感觉还是有些冗余。我们可以思考一下，当我们在第一次遍历建立哈希表的时候，每次在放入一个元素-索引对之前，我们可以先回过头来看看表中是否已经存在满足要求的元素，如果存在，查找过程结束。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> m;
        for (int i=0; i<nums.size(); i++) {
            int complement = target - nums[i];
            if (m.find(complement) != m.end()) {
                return vector<int> {m.find(complement)->second, i};
            }
            m.insert(std::make_pair(nums[i], i));
        }
        return vector<int>();
    }
};

复杂度分析：
时间复杂度：O(n)。LeetCode执行用时16ms。
空间复杂度：O(n)。LeetCode内存消耗10.5MB。

总结：
1、当算法对空间复杂度不做要求时，我们可以考虑以空间换时间，采用哈希表以O(1)的时间复杂度来查找元素；
2、学习C++ STL中的哈希表 unordered_map。

附：完整代码