解法一:暴力求解
分析:
直接两层循环,遍历数组:
第一层循环确定一个数
n1
,然后第二层循环中判断数组中是否存在target - n1
,如果存在,将{n1,n2}返回。O(n^2),会超时。
代码:
vector<int> twoSum_force(vector<int>& nums, int target) {
vector<int> result(2);
for(int i=0; i<nums.size(); i++) {
int minus = target - nums[i];
for(int j=i+1; j<nums.size(); j++) {
if(nums[j] == minus) {
result[0]=i;
result[1]=j;
return result;
}
}
}
return result;
}
解法(思路)二:
分析:
先排序,然后利用双指针,左右夹逼寻找,假如两个指针当前为
i
和j
,sum = nums[i]+nums[j]
:
- 如果sum<target,即两数的和大小不够大,让
i++
;- 如果sum>target,即两数的和过大,让
j--
;- 如果sum == target,即找到了这两个数。
排序O(nlogn),左右夹逼O(n),最终为 O(nlogn)。
如果本题结果是返回两个数,这个方法就可以使用
但是本题要求的是返回下标,排序后下标已经变化,所以行不通。
解法三:哈希表
分析:
在解法一中思想是两层循环,第一层循环确定一个数n1,去找数组中有没有另一个数n2,与n1相加结果为target。
解法一超时的原因,就是每次去找这样的一个n2,都需要遍历一遍数组,即O(n)。
最坏情况下,对数组中的每个元素都去找一遍有没有另一个数相加为target,这样就导致时间复杂度为O(n^2)。能不能利用一种机制,加速n2的查找,我们很容易可以想到,哈希表的查找时间在O(1)。
所以,在哈希表中存储数组中所有元素的下标,只需要一次遍历,遍历到
num
时,直接去哈希表中找,有没有target-num
,这样就可以让整个查找的时间复杂度降至O(n)。
tips:
如果找到了结果,需要以vector的形式返回的两个数的下标为i1,i2 //可以直接返回: return {i1,i2}; //来代替下面的: vector<int> result(2); result[0] = i1; result[1] = i2; return result;
代码:
vector <int> twoSumHash(vector<int>& nums, int target) {
//vector <int> result(2);
unordered_map<int,int> hashtable;
for(int i =0 ; i<nums.size(); i++) {
int minus = target - nums[i];
if(hashtable.count(minus)) {
//result[0]=hashtable[minus];
//result[1]=i;
return {hashtable[minus],i};
}
hashtable[nums[i]]=i;
}
return {};
}