题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
题解
备注:没有进行输入检查,默认是有效输入数据.
暴力双重循环
最简单的,一下子想到的,双重循环遍历查找,第一层i:begin->end,第二次j:i+1->end
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
for(int i = 0;i < nums.size();i++)
{
int tmp = target - nums[i];
for(int j = i + 1;j < nums.size();j++)
{
if(tmp == nums[j])
return vector<int>{i,j};
}
}
return vector<int>{-1,-1};
}
};执行用时：460 ms, 在所有 C++ 提交中击败了39.91%的用户
内存消耗：8.9 MB, 在所有 C++ 提交中击败了36.09%的用户
思考一下,使用双重循环,时间复杂度应该是在O(n^2).
哈希字典
稍加思索,感觉这种有查找的,可以使用哈希字典来提升下速度.
思路如下: 1. 遍历一次数组,将其填充到哈希字典中,key为数组值,value为数组下标.如果有重复的元素,只会记录最后一次出现的索引. 2. 遍历一次数组,查找相应值,要注意遍历时候的数组索引和.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> m;
for(int i = 0;i<nums.size();i++)
{
m[nums[i]]=i; // key:nums[i],value:i
}
for(int i = 0;i<nums.size();i++)
{
int tmp = target - nums[i];
if(m.count(tmp) > 0 && m[tmp] != i)
{
return vector<int>{i,m[tmp]};
}
}
return vector<int>{-1,-1};
}
};执行用时：16 ms, 在所有 C++ 提交中击败了75.88%的用户
内存消耗：9.9 MB, 在所有 C++ 提交中击败了10.90%的用户
从执行时间来看,应该还是有更好的解法.稍加思索,没想出来,看下题解.
哈希字典,插入时检查
来自题解:
上一个做法是先将元素插入到哈希字典中,然后再进行一轮遍历,查找想要的元素. 本做法是在插入元素的同时检查哈希字典中有无想要的值,如果有,就直接返回.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> m;
for(int i = 0;i<nums.size();i++)
{
int tmp = target - nums[i];
if(m.count(tmp) > 0)
{
return vector<int>{m[tmp],i};
}
m[nums[i]] = i;
}
return vector<int>{-1,-1};
}
};执行用时：12 ms, 在所有 C++ 提交中击败了90.15%的用户
内存消耗：9.9 MB, 在所有 C++ 提交中击败了13.00%的用户
错误思路
第一想法是排序,然后再进行查找,但是结果不对,然后才反应过来排序后数组的下标变化了.(可以做一个新的数据结构,把value和索引下标包装起来,排序后就不会丢失索引信息.)
