云南省建设工程标准定额网站,国内wordpress博客,成都专门做公司网站的公司,网页游戏排行榜源码题目描述
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是#xff0c;数组中同一个元素在答案里不能重复出现。
你可以按任…题目描述
给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
题解
暴力解法
#include iostream
#include vector
#include string
using namespace std;class Solution {
public:vectorint twoSum(vectorint nums, int target) {for(int i0;inums.size();i){for(int ji1;jnums.size();j){if(nums[i]nums[j]target){return{i,j}; //注意若return vector值要用{}}}}return {}; //return时vector若空要用{}}
};
时间复杂度为On^2,空间复杂度为O1
哈希解法
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint, int hashtable; //定义一个无序的哈希表for (int i 0; i nums.size(); i) {auto it hashtable.find(target - nums[i]);if (it ! hashtable.end()) {return {it-second, i};}hashtable[nums[i]] i;}return {};}
}; 时间复杂度为On,空间复杂度为On
分析
unordered_mapint, int hashtable; //定义一个无序的哈希表在C中unordered_map 是一个无序的哈希表实现
它允许我们存储键值对并且能够快速地根据键来查找对应的值。
键Key和值Value是一种常见的数据结构特别是在字典或哈希表、映射中。键和值之间的关系是一一对应的每个键都唯一地对应一个值。
怎么确定谁是键谁是值 唯一性键通常是唯一的而值可以是重复的。这意味着你可以使用键来快速查找、添加、修改或删除与之关联的值。 查找效率键用于快速查找对应的值。在一个优化良好的哈希表中查找一个键对应的值通常是一个常数时间操作O(1)。 数据表示键和值的具体含义取决于你正在处理的数据。例如在一个电话本应用中键可能是人名用于快速查找而值可能是与该人名关联的电话号码。 业务需求在业务逻辑中键和值的选择通常基于你的业务需求。例如如果你需要快速检索数据那么将检索条件作为键返回的结果作为值是很自然的选择。 数据模型在数据库或数据模型中键通常用于唯一标识一条记录而值则表示该记录的其他属性。 由此可以判断nums数组中的数是键下标是值
auto it hashtable.find(target - nums[i]);target-nums[i]表示查找哈希表中对应这个数nums[i]的补数的下标
it是一个迭代器
if (it ! hashtable.end()) { //如果it没有到哈希表的末尾说明找到了这个键return {it-second, i}; //那么就返回键对应的值也就是下标}
hashtable[nums[i]] i; //如果没找到这个键就把它加到哈希表里以便后续查找
一些语法提示 在C的std::unordered_map中每个元素都是一个键值对key-value pair。当你使用迭代器如it来遍历或查找哈希表中的元素时迭代器指向的是一个包含两个成员的std::pair对象这两个成员分别是first和second。
it-first代表键key即你存储在哈希表中的整数值。it-second代表值value即与键相关联的数据在这个例子中值是与数组中的整数对应的下标。 题解来源
作者力扣官方题解 链接https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/
