給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target服协，請你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)武翎，并返回他們的數(shù)組下標(biāo)蛉腌。
你可以假設(shè)每種輸入只會(huì)對應(yīng)一個(gè)答案。但是缴罗，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素助琐。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)面氓，非商業(yè)轉(zhuǎn)載請注明出處兵钮。
c++暴力破解
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
for (int i = 0; i < nums.size(); ++i)
{
for (int j=i+1;j<nums.size();j++)
{
if(nums[i]+nums[j]==target){
result.push_back(i);
result.push_back(j);
return result;
}
}
}
}
};
python暴力破解
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
ans=[]
for i in xrange(nums.__len__()):
for j in xrange(nums.__len__()):
if(j>i and nums[i]+nums[j]==target):
ans.append(i)
ans.append(j)
return ans
pytnon使用map
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
ans=[]
map = {}
for i in range(nums.__len__()):
map[(target-nums[i])]=i
print map
for i in range(nums.__len__()):
if(map.get(nums[i]) and i !=map.get(nums[i]) ):
ans=[]
ans.append(i)
ans.append(map.get(nums[i]))
return ans
c++使用map v1.0
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
map<int,int> temp;
for (int i=0;i<nums.size();i++)
{
temp[target-nums[i]]=i;
}
for (int i=0;i<nums.size();i++)
{
cout<<nums[i]<<endl;
if(temp.find(nums[i])!=temp.end()&&i!=temp[nums[i]]){//這個(gè)地方順序很重要蛆橡，原先一直報(bào)錯(cuò)，原因在于temp[nums[i]]若是不存在會(huì)自動(dòng)插入
result.push_back(i);
result.push_back(temp[nums[i]]);
return result;
}
}
}
};
c++使用map v2.0
這個(gè)版本在一個(gè)n循環(huán)都不到的時(shí)間中就可以實(shí)現(xiàn)
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
map<int,int> temp;
for (int i=0;i<nums.size();i++)
{
if (temp.count(target-nums[i])&&i!=temp[target-nums[i]]){
result.push_back(temp[target-nums[i]]);//temp[target-nums[i]]肯定在前面
result.push_back(i); //i肯定在后面
return result;
}
temp[nums[i]]=i;
}
}
python使用dict 版本
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
tmp={}
result=[]
for i,number in enumerate(nums):
if(number in tmp):
result.append(tmp[number])
result.append(i)
break
else:
tmp[target-number]=i # 鍵存儲(chǔ)的是差值掘譬，值存儲(chǔ)第一個(gè)數(shù)序號
return result
代碼更簡潔的python3版本
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
tmp={}
for i,number in enumerate(nums):
if(number in tmp):
return [tmp[number],i]
else:
tmp[target-number]=i # 鍵存儲(chǔ)的是差值泰演，值存儲(chǔ)第一個(gè)數(shù)序號
java版本
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> tmp=new HashMap(); // java版本主要是對map的操作不熟悉，太麻煩了葱轩，一定要IDE
for (int i=0;i<nums.length;i++){
if(tmp.containsKey(nums[i])) return new int[] {tmp.get(nums[i]),i};
else tmp.put(target-nums[i],i);
}
return null;
}
}
注意事項(xiàng)
1.使用map會(huì)使得效率提高很多睦焕，主要是特殊的數(shù)據(jù)結(jié)構(gòu)使得查找的效率很高
2.java中的hashMap底層用了hash表，TreeMap用了紅黑樹靴拱，python中的dict{}應(yīng)該是采用哈希表垃喊，最低能在O(1)時(shí)間內(nèi)完成搜索，c++中map使用的應(yīng)該是紅黑樹
3.temp[nums[i]]這里要注意袜炕，若是不存在的話會(huì)自動(dòng)插入0本谜，就是一個(gè)簡單的cout<<temp[4]，都會(huì)添加一個(gè)新元素導(dǎo)致很隱秘的錯(cuò)誤偎窘。耕突。。评架。
參考資料
1.python的dict實(shí)現(xiàn)[http://www.reibang.com/p/02af9673ab34]
2.Java HashMap工作原理及實(shí)現(xiàn)
[http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/]
