问题: 给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例:给定 nums = [2, 7, 11, 15], target = 9。因为 nums[0] + nums[1] = 2 + 7 = 9,所以返回 [0, 1]
看到这一题,大家脑海里蹦出来的第一个想法应该是暴力做法,即遍历数组,并查找是否存在一个值与target-x相等的目标元素。
1class Solution {
2public:
3 vector<int> twoSum(vector<int>& nums, int target) {
4 int i,j;
5 for(i=0;i<nums.size()-1;i++)
6 {
7 for(j=1;j<nums.size();j++)
8 {
9 if(nums[i]+nums[j]==target)
10 return {i,j};
11 }
12 }
13 return {};
14 };
15};
为了对时间复杂度进行优化,我们需要一种时间复杂度更低的方法来查找数组是否存在目标元素。而查找索引一个非常有效的方法就是哈希表。
我们通过以空间换取时间的方式,可以将查找时间从O(n)降低到O(1)。哈希表支持以近似恒定的时间进行快速查找。之所以用近似,是因为一旦出现冲突,查找时间复杂度可能退化为O(n),这取决于你选择的哈希函数。
我们在第一次的遍历中,将每个元素的value和它的key添加到哈希表中。然后在第二次遍历中,我们将检查每个元素对应的目标元素(target-nums[i])是否存在表中,另外我们也需要注意目标元素不能是nums[i]本身。
1class Solution {
2public:
3 vector<int> twoSum(vector<int>& nums, int target) {
4 map<int,int> a;//建立hash表存放数组元素
5 vector<int> b(2,-1);//存放结果
6 for(int i=0;i<nums.size();i++)
7 a.insert(map<int,int>::value_type(nums[i],i));
8 for(int i=0;i<nums.size();i++)
9 {
10 if(a.count(target-nums[i])>0&&(a[target-nums[i]]!=i))
11 //判断是否找到目标元素且目标元素不能是本身
12 {
13 b[0]=i;
14 b[1]=a[target-nums[i]];
15 break;
16 }
17 }
18 return b;
19 };
20};
我们仔细想想就可以明白,其实我们只需要遍历一次哈希表。我们在插入元素的同时就可以判断表中是否存在目标元素,如果已经存在,我们就可以返回我们的解。
1class Solution {
2public:
3 vector<int> twoSum(vector<int>& nums, int target) {
4 map<int,int> a;
5 vector<int> b(2,-1);
6 for(int i=0;i<nums.size();i++)
7 {
8 if(a.count(target-nums[i])>0)
9 {
10 b[0]=a[target-nums[i]];
11 b[1]=i;
12 break;
13 }
14 a[nums[i]]=i;
15 }
16 return b;
17 };
18};