算法-每日一题(DAY13)两数之和

发布于:2025-08-19 ⋅ 阅读:(13) ⋅ 点赞:(0)

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

当前索引 i nums[i] 补数 complement = target - nums[i] 字典 num_map 内容(值:索引) 操作说明
0 2 9−2=7 {} 字典中无键 
7,存入
1 7 9−7=2 {2:0} 找到补数!返回 [num_map[2], 1] → [0, 1]

6.复杂度计算:

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

哈希法:时间复杂度为O(n),空间复杂度为O(n)。


网站公告

今日签到

点亮在社区的每一天
去签到