只会写暴力解法，学习下高等算法
三种方法（暴力、双指针、哈希）
C++
1.暴力
暴力算法时间复杂度O（n²），空间复杂度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;
}
};
2.排序+双指针法
这里先将数组排序好O（nlogn），再利用双指针法遍历一遍O（n）得到结果。
为了保存下标信息另开了一个数组
时间复杂度O（nlogn），空间复杂度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;
}
};
3.hash法
利用undered_map数组构造映射，遍历nums[i]时，看target-nums[i]是否存在hash表中即可
时间复杂度O（n），空间复杂度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){
//防止利用同个元素
ans.push_back(i);
ans.push_back(hashmap[target-nums[i]]-1);
return ans;
}
hashmap[nums[i]]=i+1;
//将hash表对应下标＋1，防止处理下标为0的情况
}
return ans;
}
};
总结：
实际在提交过程中，方法2,3差距不太，1最慢。
Python
暴力
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i]+nums[j]==target:
return [i,j]
return []
排序＋双指针
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
temp=nums.copy()
temp.sort()
i=0
j=len(nums)-1
while i<j:
if (temp[i]+temp[j])>target:
j=j-1
elif (temp[i]+temp[j])<target:
i=i+1
else:
break
p=nums.index(temp[i])
nums.pop(p)
k=nums.index(temp[j])
if k>=p:
k=k+1
return [p,k]
hash
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashset={}
for i in range(len(nums)):
if hashset.get(target-nums[i]) is not None :
return [hashset.get(target-nums[i]),i]
hashset[nums[i]]=i
作者：yun-yu-chen
链接：https://leetcode-cn.com/problems/two-sum/solution/san-chong-fang-fa-bao-li-shuang-zhi-zhen-ha-xi-san/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
