建设部科研申报网站用着不好,怎么在服务器中安装WordPress,开发公司挖出的沙子归谁,黄页88网官网链接两数之和题序号1题型数组解题方法1. 哈希表#xff0c;2. 暴力法难度简单熟练度✅✅✅✅✅
题目 给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。 你可以假设每种输…链接两数之和题序号1题型数组解题方法1. 哈希表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 只会存在一个有效答案 进阶 你可以想出一个时间复杂度小于 O(n2) 的算法吗 题解 核心思想 使用一个哈希表来存储数组元素及其对应的下标。键是数组元素值是元素的下标。遍历数组对于每个元素 nums[i]计算 complement target - nums[i]。检查 complement 是否在哈希表中。如果在说明找到了两个数它们的和为 target直接返回它们的下标如果不在将当前元素 nums[i] 及其下标 i 存入哈希表。 复杂度时间复杂度O(N)空间复杂度O(N)。 c 实现算法
vectorint twoSum(vectorint nums, int target) {unordered_mapint, int numMap; // 用于存储数字和它的索引//遍历数组 nums从索引 i 0 开始直到数组的最后一个元素for (int i 0; i nums.size(); i) {int complement target - nums[i]; // 计算当前数字需要的补数//检查哈希表中是否存在补数 complement。如果找到了表示我们已经找到了一对数字//它们的和为 target。find 函数用于查找哈希表中是否存在给定的键complement。//如果存在find 会返回一个指向该元素的迭代器否则返回 end()。if (numMap.find(complement) ! numMap.end()) {return {numMap[complement], i}; // 返回补数的索引和当前数字的索引找到了就直接返回不需要继续找了}//它的键是数组中的元素值是该元素的索引。//通过 numMap[nums[i]] i我们将当前元素 nums[i] 的值作为键将其索引 i 作为值存储在哈希表中。numMap[nums[i]] i; }return {}; // 如果没有找到符合条件的结果返回空数组
}算法推演 假设输入数组 nums [2, 7, 11, 15] 和目标值 target 9。 步骤 1初始化哈希表 unordered_mapint, int numMap; 这里创建了一个哈希表 numMap它的键key是数组中的元素值value是该元素的索引。哈希表的作用是快速查找数组中是否已经存在与当前数字相加等于目标值的数字。 步骤 2遍历数组 我们开始遍历数组 nums。 第一次迭代i 0nums[i] 2 计算补数complement target - nums[0] 9 - 2 7。 检查哈希表中是否有 complement 7 numMap.find(7) 返回 numMap.end()表示没有找到补数。 将 nums[0] 2 和它的索引 0 存入哈希表numMap[2] 0。 当前哈希表状态numMap {2: 0}。第二次迭代i 1nums[i] 7 计算补数complement target - nums[1] 9 - 7 2。 检查哈希表中是否有 complement 2 numMap.find(2) 返回 numMap[2] 0表示找到了补数 2它的索引是 0。 找到符合条件的两个数字nums[0] 2 和 nums[1] 7它们的和是 9。 返回这两个索引return {numMap[2], 1}即返回 [0, 1]。 c 完整 demo
#include iostream
#include vector
#include unordered_map
using namespace std;vectorint twoSum(vectorint nums, int target) {unordered_mapint, int numMap; // 用于存储数字和它的索引//遍历数组 nums从索引 i 0 开始直到数组的最后一个元素for (int i 0; i nums.size(); i) {int complement target - nums[i]; // 计算当前数字需要的补数//检查哈希表中是否存在补数 complement。如果找到了表示我们已经找到了一对数字//它们的和为 target。find 函数用于查找哈希表中是否存在给定的键complement。//如果存在find 会返回一个指向该元素的迭代器否则返回 end()。if (numMap.find(complement) ! numMap.end()) {return {numMap[complement], i}; // 返回补数的索引和当前数字的索引找到了就直接返回不需要继续找了}//它的键是数组中的元素值是该元素的索引。//通过 numMap[nums[i]] i我们将当前元素 nums[i] 的值作为键将其索引 i 作为值存储在哈希表中。numMap[nums[i]] i; }return {}; // 如果没有找到符合条件的结果返回空数组
}int main() {vectorint nums {2, 7, 11, 15};int target 9;vectorint result twoSum(nums, target);if (!result.empty()) {cout Indices: result[0] , result[1] endl;} else {cout No solution found! endl;}return 0;
}
