高大上的企业网站,wordpress动态图,在线个人网站,上海东道设计题目描述#xff1a;
给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。
要求#xff1a;
可以假设每种输入只会对应一个答案#xff0c;并且你不能使用两次相同的元素…题目描述
给定一个整数数组 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]
解答
方法一、暴力枚举
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int result_i0,result_j0;for(int i0;inums.size();i){for(int j0;jnums.size();j){if(nums[i]nums[j] target j!i){result_i i;result_j j;break;}}}std::vectorint result;result.push_back(result_i);result.push_back(result_j);return result;}
};方法二、哈希表:
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint,int hashtable;for(int i0;inums.size();i){auto ithashtable.find(target-nums[i]);if(it !hashtable.end()){return{it-second,i};}hashtable[nums[i]]i;}return {};}
};哈希表的特性
(1)查找时复杂度为O(1)
(2)使用insert插入元素时第一次insert成功第二次insert不能将第一次的值覆盖
(3)使用索引赋值时能将元素进行有效更新。
例
#includeunordered_map// 初始 map 的内容为{{11}{22},{3,3}}
unordered_mapint, int map{{1,1},{2,2},{3,3}};
//修改第3个元素
map[3]4;
// map的内容更新为{{11}{22},{3,4}}
// 插入新元素
map.insert({4,10});
// map的内容更新为{{11}{22},{3,4},{4,10}}
// 试图修改map第4个元素的值
map.insert({4,20});
// map的内容仍为{{11}{22},{3,4},{4,10}}
