解法一：暴力求解
分析：
直接兩層回圈，遍歷陣列：
第一層回圈確定一個數
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 {};
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/285757.html
標籤：其他