題目：
? 給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，并回傳他們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素不能使用兩遍，
示例:
? 給定 nums = [2, 7, 11, 15], target = 9
? 因為 nums[0] + nums[1] = 2 + 7 = 9
? 所以回傳 [0, 1]
解題思路：
? 題目的條件即找到兩數之和為給定的數字就停止查找，一般思路，就是直接遍歷二重回圈，i 和 j分別表示加數，找到對應和為給定值，然后回傳下標，時間復雜度是O（n^2），優化思路：可以利用hash表，提前存盤陣列的值，用空間換時間，這樣，因為理想情況下，hash表的一次查找的時間復雜度是O（1），所以只要遍歷一次hash 表，找到符合條件的，和為給定值的另一個數，回傳下標
代碼：
? 一般思路：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i, j;
for (int i = 0; i < nums.size() - 1; i++) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
return {i, j};
}
};
? hash優化： 先存盤到hash表里，然后一次遍歷找另一個加數，由于這里只是要求回傳下標，因此hash表記憶體儲下標就可以，map（數字，下標）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); i++) {
if (hash.count(target - nums[i])) { //找到另一個加數
return {hash[target - nums[i]], i};
}
hash[nums[i]] = i; //每次遍歷都把下標存進hash表
}
}
return {-1, -1};
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/54297.html
標籤：AI