LeetCode 力扣热题 100道（一）两数之和（C++）

两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

第一种方法比较常规暴力枚举，时间复杂度： O(n^2)，因为我们使用双重循环遍历数组，每次检查一对元素的和。

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 {i,j};
                }
            }
        }
        return {};
    }
};

第二种方法哈希表解法，时间复杂度： O(n)，因为我们只遍历一次数组，对于每个元素的查找和插入操作，哈希表的时间复杂度是常数 O(1)。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> num_map;
         for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i]; 
            if (num_map.find(complement) != num_map.end()){
                 return {num_map[complement], i};
            }
            num_map[nums[i]] = i;
         }
        return {};
    }
};

假设 nums = [2, 7, 11, 15]，目标值 target = 9。

第一轮：
- 当前元素是 nums[0] = 2，计算 complement = 9 - 2 = 7。
- 哈希表 num_map 为空，7 不在哈希表中。
- 将当前元素 nums[0] = 2 存入哈希表：num_map = {2: 0}。
第二轮：
- 当前元素是 nums[1] = 7，计算 complement = 9 - 7 = 2。
- 哈希表 num_map = {2: 0}，发现 complement = 2 在哈希表中，说明 nums[0] + nums[1] = 9。
- 返回结果：{0, 1}。

如何用哈希表来找到两个数？

问题的核心思想： 对于每一个元素 nums[i]，我们希望在之前遍历的数组元素中，找到一个数 complement，使得 nums[i] + complement = target，从而满足题目条件。也就是：
complement=target−nums[i]\text{complement} = \text{target} - \text{nums}[i]complement=target−nums[i]
这样，我们就可以通过查找哈希表中是否存在 complement 来判断是否找到了匹配的两个数。
为什么哈希表有效？
- 哈希表是一个常数时间查找结构： 使用哈希表存储之前遍历过的元素，每个元素和其下标都作为键值对存储。查找一个元素是否在哈希表中存在的时间复杂度为 O(1)。
- 早期发现匹配： 在遍历数组时，我们可以在当前元素 nums[i] 被处理之前，检查 target - nums[i] 是否已经出现在哈希表中。这样，查找操作变得非常高效，我们能快速确定某个值是否已经出现在数组的前面部分。
解释为什么能找到配对：
- 思考过程： 对于每一个元素 nums[i]，我们在遍历过程中都计算出当前元素和目标值的差值 complement = target - nums[i]。然后我们查找哈希表中是否存在 complement，如果存在，就说明存在两个数，它们的和为 target。
- 哈希表的作用： 哈希表的作用是记录我们已经遍历过的元素，所以当我们遇到某个元素时，我们只需要查找它的差值是否已经存在。这样就可以快速找到一对数。
为什么可以在 O(n) 时间内找到答案：
- 一遍扫描： 在遍历数组时，我们只需要对每个元素进行一次查找和插入操作，且每次查找和插入的时间复杂度是常数 O(1)。
- 不需要重复扫描： 不像暴力解法需要两层循环去遍历数组的每一对元素，哈希表方法只需要遍历一次数组。