題目鏈接
tag:
- Easy俗孝；
question:
??Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
思路：
??本道題給一個數組斋否，一個目標數target怨咪，讓我們找到兩個數字，使其和為target孟抗，第一感覺暴力搜索迁杨，但是猜到OJ肯定不會允許用這么簡單的方法，于是去試了一下夸浅，果然是Time Limit Exceeded仑最，這個算法的時間復雜度是O(n^2)扔役。那么只能想個O(n)的算法來實現帆喇，由于暴力搜索是遍歷所有的兩個數字的組合，這樣雖然節(jié)省了空間亿胸，但時間復雜度高坯钦。一般來說预皇，我們?yōu)榱颂岣邥r間的復雜度，需要用空間來換婉刀，這算是一個trade-off吧吟温，用線性的時間復雜度來解決問題，那么就是說只能遍歷一個數字突颊，那么另一個數字呢鲁豪，我們可以事先將其存儲起來，使用一個HashMap律秃，來建立數字和其坐標位置之間的映射爬橡，HashMap是常數級的查找效率，這樣棒动，我們在遍歷數組的時候糙申，用target減去遍歷到的數字，就是另一個需要的數字了船惨，直接在HashMap中查找其是否存在即可柜裸，注意要判斷查找到的數字不是第一個數字，比如target是4粱锐，遍歷到了一個2疙挺，那么另外一個2不能是之前那個2，整個實現步驟為：先遍歷一遍數組怜浅，建立HashMap映射衔统，然后再遍歷一遍，開始查找海雪，找到則記錄index锦爵。代碼如下：
C++ 解法：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 兩次遍歷+哈希
vector<int> res;
unordered_map<int, int> m;
if (nums.size() < 2)
return res;
for (int i=0; i<nums.size(); ++i)
m[nums[i]] = i;
for (int i=0; i<nums.size(); ++i) {
int tmp = target - nums[i];
if (m.count(tmp) && m[tmp] != i) {
res.push_back(i);
res.push_back(m[tmp]);
break;
}
}
return res;
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 一次遍歷+哈希
vector<int> res;
if (nums.size() < 2) {
return res;
}
unordered_map<int, int> m;
for (int i = 0; i < nums.size(); ++i) {
int tmp = target - nums[i];
if (m.count(tmp) && m[tmp] != i) {
res.push_back(i);
res.push_back(m[tmp]);
break;
}
m[nums[i]] = i;
}
return res;
}
};
Python 解法：
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
res = []
if len(nums) < 2:
return res
m = {}
for i in range(len(nums)):
m[nums[i]] = i
for i in range(len(nums)):
diff = target - nums[i]
if diff in m.keys() and (i != m[diff]):
res.append(i)
res.append(m[diff])
break
return res
