算法-每日一题（DAY13）两数之和

1.题目链接：

1. 两数之和 - 力扣（LeetCode）

2.题目描述：

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

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

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

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

3.解题思路：

（1）暴力枚举：

我们采用双重循环的思路，通过外层循环和内层循环来查找数组中两数之和等于目标值target的元素对。外层循环指针i遍历数组的每个元素，内层循环指针j从i+1开始，避免重复检查已经处理过的元素对。在每次循环中，检查nums[i] + nums[j]是否等于target，若成立，说明找到了符合条件的元素对，直接返回它们的索引i和j。如果循环结束没有找到满足条件的元素对，则返回一个空数组。通过这种方式，代码遍历了所有可能的元素对，最终返回满足条件的两个索引。

（2）哈希：

我们采用哈希表的思路，通过存储数组元素的值及其对应的索引，快速查找是否存在符合条件的两个数。在遍历数组的过程中，计算当前元素nums[i]的补数（即target - nums[i]）。每次遍历时，首先检查补数是否已经出现在哈希表中。如果找到了补数，说明找到了符合条件的两个数，直接返回它们的索引；如果没找到补数，则将当前元素及其索引加入哈希表，继续遍历下一个元素。通过这种方式，代码仅需一次遍历就能够找到符合条件的元素对，极大地提高了效率。

4.题解代码：

这是暴力枚举的代码，也是最容易想到最简单的代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        // 获取数组nums的大小
        int n = nums.size(); 
        // 外层循环遍历每个元素
        for (int i = 0; i < n; i++)
        {
            // 内层循环从当前位置i+1开始，避免重复检查已处理过的元素对
            for (int j = i + 1; j < n; j++)
            {
                // 检查nums[i]和nums[j]的和是否等于目标值target
                if (nums[i] + nums[j] == target)
                {
                    // 如果找到了匹配的元素对，返回它们的索引
                    return{ i, j };
                }
            }
        }

        // 如果没有找到满足条件的元素对，返回空数组
        return { };
    }
};

这是哈希的代码，用空间换时间，时间复杂度更低

vector<int> twoSum(vector<int>& nums, int target) 
{
    // 创建一个哈希表，用来存储数组元素的值及其对应的索引
    unordered_map<int, int> hash_map; // 值->索引映射

    // 遍历数组 nums 中的每个元素
    for (int i = 0; i < nums.size(); ++i) 
    {
        // 计算当前元素 nums[i] 的补数（即 target - 当前元素）
        int complement = target - nums[i];
        
        // 检查补数是否已经在哈希表中存在
        if (hash_map.find(complement) != hash_map.end()) 
        {
            // 如果找到了补数，说明找到了符合条件的两个数
            // 返回补数的索引和当前元素的索引
            return {hash_map[complement], i};
        }
        
        // 如果补数不存在，将当前元素 nums[i] 和它的索引 i 存入哈希表
        hash_map[nums[i]] = i;
    }
    
    // 如果遍历完成后没有找到符合条件的两个数，返回空的 vector
    return {}; 
}

5.示例演算：

假设输入：
nums = [2, 7, 11, 15], target = 9

6.复杂度计算：

暴力法：时间复杂度为O(n^2)，空间复杂度为O(1)。

哈希法：时间复杂度为O(n)，空间复杂度为O(n)。