1.首先想到的方法就是两个for循环全部遍历,代码如下,可通过,但效率太低
class Solution
{
public:
vector<int> twoSum(vector<int> nums, int target)
{
vector<int> res;
for (int i = ; i < nums.size(); i++)
{
for (int j = i + ; j < nums.size(); j++)
{
if (nums[j] == target - nums[i])
{
res.push_back(i);
res.push_back(j);
}
}
}
return res;
}
};
2.使用unordered_map,遍历vector中每个元素,并在hash表中通过find()查找目标元素,若找到则写入结果,否则将当前元素加入到hash表中。(每次调用find()函数是为了判断当前元素与其前面的元素之和是否为target值)。
class Solution
{
public:
vector<int> twoSum(vector<int> nums, int target)
{
unordered_map<int,int> hash;
vector<int> res;
for (int i = ; i < nums.size(); i++)
{
int numTofind = target - nums[i]; if(hash.find(numTofind) != hash.end())
{
res.push_back(hash[numTofind]);
res.push_back(i);
}
else
{
hash[nums[i]] = i;
}
}
return res;
} };