Python
- 方法一：用 Python 中 list 的相關(guān)函數(shù)求解
num2 = target - num1增显，是否也在 list 中，那么就需要運(yùn)用以下兩個(gè)方法：
num2 in nums拿霉，返回 True 說明有戲
nums.index(num2)，查找 num2 的索引
900ms 13.4MB
def twoSum(nums, target):
lens = len(nums)
j=-1
for i in range(lens):
if (target - nums[i]) in nums:
if (nums.count(target - nums[i]) == 1)&(target - nums[i] == nums[i]):
continue
else:
j = nums.index(target - nums[i],i+1) #index(x,i+1)是從num1后的序列后找num2
break
if j>0:
return [i,j]
else:
return []
- 方法二：
num2 的查找并不需要每次從 nums 查找一遍咱扣，只需要從 num1 位置之前或之后查找即可绽淘。但為了方便 index 這里選擇從 num1 位置之前查找，執(zhí)行通過偏窝，耗時(shí)縮短一半多收恢，共 702ms。
def twoSum(nums, target):
lens = len(nums)
j=-1
for i in range(1,lens):
temp = nums[:i]
if (target - nums[i]) in temp:
j = temp.index(target - nums[i])
break
if j>=0:
return [j,i]
- 方法三：用字典模擬哈希求解
通過哈希來求解祭往，這里通過字典來模擬哈希查詢的過程。通過字典的方法火窒，查找效率快很多硼补，執(zhí)行速度大幅縮短，共 32ms熏矿。
def twoSum(nums, target):
hashmap={}
for ind,num in enumerate(nums):
hashmap[num] = ind
for i,num in enumerate(nums):
j = hashmap.get(target - num)
if j is not None and i!=j:
return [i,j]
- 方法四：類似方法二已骇，不需要 mun2 不需要在整個(gè) dict 中去查找∑北啵可以在 num1 之前的 dict 中查找褪储，因此就只需要一次循環(huán)可解決。不過方法四相較于方法三的運(yùn)行速度沒有像方法二相較于方法一的速度提升慧域。運(yùn)行速度在 70ms 多鲤竹。
def twoSum(nums, target):
hashmap={}
for i,num in enumerate(nums):
if hashmap.get(target - num) is not None:
return [i,hashmap.get(target - num)]
hashmap[num] = i #這句不能放在if語句之前，解決list中有重復(fù)值或target-num=num的情況
作者：lao-la-rou-yue-jiao-yue-xiang
鏈接：https://leetcode-cn.com/problems/two-sum/solution/xiao-bai-pythonji-chong-jie-fa-by-lao-la-rou-yue-j/
來源：力扣（LeetCode）
著作權(quán)歸作者所有昔榴。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)辛藻，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
C++
- 方法一：暴力
暴力算法時(shí)間復(fù)雜度O（n2）互订，空間復(fù)雜度O（1）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
if(nums[i]+nums[j]==target){
ans.push_back(i);
ans.push_back(j);
return ans;
}
}
}
return ans;
}
};
- 方法二：排序+雙指針法
這里先將數(shù)組排序好O（nlogn）吱肌，再利用雙指針法遍歷一遍O（n）得到結(jié)果。
為了保存下標(biāo)信息另開了一個(gè)數(shù)組
時(shí)間復(fù)雜度O（nlogn）仰禽，空間復(fù)雜度O（n）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
vector<int> temp;
temp=nums;
int n=temp.size();
sort(temp.begin(),temp.end());
int i=0,j=n-1;
while(i<j){
if(temp[i]+temp[j]>target)j--;
else if(temp[i]+temp[j]<target)i++;
else break;
}
if(i<j){
for(int k=0;k<n;k++){
if(i<n&&nums[k]==temp[i]){
ans.push_back(k);
i=n;
}
else if(j<n&&nums[k]==temp[j]){
ans.push_back(k);
j=n;
}
if(i==n&&j==n)return ans;
}
}
return ans;
}
};
- 方法三：hash法
利用undered_map數(shù)組構(gòu)造映射氮墨，遍歷nums[i]時(shí)纺蛆，看target-nums[i]是否存在hash表中即可
時(shí)間復(fù)雜度O（n），空間復(fù)雜度O（n）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
unordered_map<int,int>hashmap;
for(int i=0;i<nums.size();i++){
if(hashmap[target-nums[i]]
&&hashmap[target-nums[i]]!=i+1){
//防止利用同個(gè)元素
ans.push_back(i);
ans.push_back(hashmap[target-nums[i]]-1);
return ans;
}
hashmap[nums[i]]=i+1;
//將hash表對(duì)應(yīng)下標(biāo)＋1规揪，防止處理下標(biāo)為0的情況
}
return ans;
}
};
總結(jié)：
實(shí)際在提交過程中犹撒，方法2,3差距不太，1最慢粒褒。
作者：yun-yu-chen
鏈接：https://leetcode-cn.com/problems/two-sum/solution/san-chong-fang-fa-bao-li-shuang-zhi-zhen-ha-xi-san/
來源：力扣（LeetCode）
著作權(quán)歸作者所有识颊。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處奕坟。
