关于LeetCode的初探----两数之和
程序员文章站
2022-05-20 12:26:43
...
题目大意:给定一个数组以及某个整数和n,应当在数组中找到两个数和为n,并且返回对应的数组下标
解题思路:
1.暴力法
2.利用map(分为两种思路,一为先循环定制好map,然后在map中查找,二为在每次设定键值对之前在map中查找是否存在符合条件的键值对)
1. 暴力法
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for(int i=0;i<nums.size();i++)
for(int j=i+1;j<nums.size();j++)
if(nums[i]+nums[j]==target)
return vector<int> {i,j};
return vector<int> {};
}
};
2.利用map的两种方法
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> hash;
for(int i=0;i<nums.size();i++)//存键值对
hash[nums[i]]=i;
for(int i=0;i<nums.size();i++)
{
int temp=target-nums[i];
if(hash.find(temp)!=hash.end()&&hash[temp]!=i)//确保存在且不重复
return vector<int>{i,hash.find(temp)->second};//我们需要的不是元素是下标
}
return vector<int>{};//表示没有找到,返回空的数组
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> hash;
for(int i=0;i<nums.size();i++)
{
int temp=target-nums[i];
if(hash.find(temp)!=hash.end())
return vector<int> {i,hash.find(temp)->second};
hash[nums[i]]=i;
}
return vector<int>{};
}
};
经过比较,暴力法自不必说,时间复杂度为O(n2),不是我们所期望的,第二种方法的时间复杂度都是O(n),但相比之下,实现2更为巧妙(利用了map中的元素不会相同减少了判断),同时,仅仅一个循环也更加的快,超推荐!
附:关于hash.find()的说明,其返回值是被查找元素的位置,如果没有就返回map.end(),当然,这里的map可以任意定义。
小菜鸡第一次写博客,如有理解有误的地方,请多多包涵。
上一篇: 深入解析Python中的descriptor描述器的作用及用法
下一篇: apache缓存如何清理