当前位置：首页 > web >正文

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

web 2025/8/19 8:31:41

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]的和是否等于目标值targetif (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;}// 如果遍历完成后没有找到符合条件的两个数，返回空的 vectorreturn {}; 
}