两数之和 - 暴力枚举+哈希表

两数之和原题地址

方法一：暴力枚举

首先，我们需要枚举数组中所有可能的下标对组合，对于n个数的数组，从中选2个下标，有种可能。做法很简单，遍历数组中的所有元素，对于每一个元素，遍历该元素后面的所有元素即可。

比如，对于4个元素的数组，下标是0~3，所有可能的组合就是：(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)，总共有种可能。

// 方法一：暴力枚举
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();

        // 对外层循环的每一个元素，遍历它们后面的元素，组成一对
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                // 判断下标对(i,j)是否满足条件
                if (nums[i] + nums[j] == target)
                {
                    return { i, j };
                }
            }
        }

        // 不存在满足条件的下标对
        return {};
    }
};

方法二：哈希表

暴力枚举的方法时间效率太低了，最坏的情况要把任意两个数都匹配一次。我们可以考虑把数组中的元素都存储到哈希表中，遍历数组中的元素，查找哈希表中是否有元素和数组中的元素匹配。

再具体一点，对于数组中的某一个元素，如果哈希表中有与之匹配的元素，就找到了符合题目要求的答案；如果没有元素与之匹配，就把这个元素存储在哈希表中。这样的话，对于数组中的每一个元素，只需要O(1)的时间复杂度就能匹配完，效率大大提升了。

C++中，需要使用unordered_map，而不是unordered_set，因为最终要返回的是数组的下标，所以要把数组的元素和对应的下标都存储到哈希表中。

// 方法二：哈希表
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 由于要返回下标，所以下标和元素都要存储
        unordered_map<int, int> hashtable;

        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            // 对于每个元素，查找哈希表中是否存在匹配的元素
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end())
            {
                // 找到了
                return { i, it->second };
            }

            // 插入元素及下标
            hashtable[nums[i]] = i;
        }

        // 不存在满足条件的下标对
        return {};
    }
};