- 題目如下
- 思路及演算法
題目只讓我們輸出一個答案，所以我們只需依次遍歷，得到答案便回傳即可
暴力破解法
由給出的串列，我們依次對其進行迭代時，對于所得到的數num時，我們會思考target-num是否在串列中
所以我們一般會對其進行雙重回圈，第一次先得到一個未知數num，第二次我們再對串列中該數后的數查找是
否有target-num(num前的元素已和num匹配可以忽略)，有則回傳兩數索引，無則回傳空串列
代碼
python代碼
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i] == target - nums[j]:
return [i,j]
return []
C++代碼
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int length = nums.size();
for(int i=0;i<length;i++){
for(int j=i+1;j<length;j++){
if(nums[i] == target - nums[j]){
return {i,j};
}
}
}
return {};
}
};
時間復雜度：O(N^2)
情況最壞的時候每個數都要匹配，這種方法在資料量很大的時候會大大增加程式運行時間，故不推薦使用
為了提搞程式運行效率，我們需要對演算法進行改善
哈希表法
哈希表我們將會在后面的資料結構與演算法中提到
我們將所給陣列的索引與數值存盤至哈希表中，往后每迭代一次便在哈希表中尋找是否有與target-num相
等的數值，若有則將兩數索引回傳，若無則回傳空
Python代碼
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hashmap = {}
for index,value in enumerate(nums):
anotherValue = target - value
if anotherValue in hashmap:
return [hashmap[anotherValue],index]
hashmap[value] = index
return None
C++代碼
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashtable;
for (int i = 0; i < nums.size(); ++i) {
auto it = hashtable.find(target - nums[i]);
if (it != hashtable.end()) {
return {it->second, i};
}
hashtable[nums[i]] = i;
}
return {};
}
};
注：該C++代碼來自官方解法
時間復雜度：O(N)
在這里我們學會了python中內置的 enumerate() 函式
enumerate() 函式用于將一個可遍歷的資料物件(如串列、元組或字串)組合為一個索引序列，同時列出資料和資料下標，一般用在 for 回圈當中，
代碼解釋來自菜鳥教程
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/272242.html
標籤：python
上一篇：Java-靜態代理與動態代理詳解