• 欢迎光临~

day1 -> 两数之和(哈希表方法)

开发技术 开发技术 2022-05-24 次浏览
/*
题目要求:

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target  的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例:

输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1]

*/

#include <iostream> #include <vector> #include <map> using namespace std; class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { map<int, int> map_a; vector<int> vec_b(2, -1); //申请一个vector,大小是2,初始化内容是-1 for(int i = 0;i < nums.size();++i) { map_a.insert(map<int, int>::value_type(nums[i], i)); } for(int i = 0;i < nums.size();++i) { if(map_a.count(target - nums[i]) != 0 && map_a[target - nums[i]] != i) { vec_b[0] = i; vec_b[1] = map_a[target - nums[i]]; } } return vec_b; } }; void printVector(vector<int> vec) { for(vector<int>::iterator it = vec.begin(); it != vec.end();it++) { cout << *it << " "; } } int main() { Solution S; vector<int> vec, vec_1; int n; cin >> n; for(int i = 0;i < n;++i) { int temp = 0; cin >> temp; vec.push_back(temp); } vec_1 = S.twoSum(vec, 6); printVector(vec_1); return 0; }

心得:

哈希表的使用场景:需要快速的判断出一个元素有木有出现在集合里,需要使用哈希表

集中数据结构:

day1 -&gt; 两数之和(哈希表方法)

 

day1 -&gt; 两数之和(哈希表方法)

 

 可以发现unordered_set与unordered_map底层是使用哈希表实现的,map和set底层是使用红黑树实现的。

 

程序员灯塔
转载请注明原文链接:day1 -> 两数之和(哈希表方法)
喜欢 (0)