算法日常・每日刷题--＜哈希＞1

1. 两数之和 - 力扣LeetCode1. 两数之和 - 给定一个整数数组 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) 的算法吗https://leetcode.cn/problems/two-sum/一、题目回顾给定整数数组nums和目标值target找出数组中相加等于target的两个数字返回二者下标。输入保证唯一解同一个元素不能使用两次下标返回顺序不限。二.解法思想空间换时间暴力双层循环时间复杂度 \(O(n^2)\)大数据场景效率低下。 我们借助哈希表unordered_map将查询操作平均时间降到 \(O(1)\)整体时间复杂度优化至 \(O(n)\)。哈希表存储映射关系数组元素值 → 元素下标遍历流程设当前遍历元素nums[i]计算互补值k target - nums[i]查询哈希表中是否存在互补值k存在直接返回{哈希表中k对应的下标, 当前下标i}不存在把当前nums[i]和下标插入哈希表留给后续元素匹配。⚠️ 关键顺序先查询后插入如果先插入再查询会读取刚存入的当前元素造成同一个元素重复使用违反题目要求。#includeunordered_map class Solution { public: vectorint twoSum(vectorint nums, int target) { int nnums.size(); unordered_mapint,int hash(n); for(int i0;in;i) { int ktarget-nums[i]; if(hash.count(k)0) { return {hash[k],i}; } hash.insert({nums[i],i}); } return {-1,-1}; } };