【Leetcode哈希+no双指针】1. 两数之和（有关于数组set还是map的选择，为什么不能用双指针！！）

• Leetcode1
• • 1.问题描述
  • 2.解决方案
  • • 解法一：暴力
    • 解法二：哈希
  • 3.关于数组set还是map的选择
  • 4.为什么不能用双指针

暴力遍历，时间复杂度o(n2)

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        vector ans;
        for(int i=0;i 

 
解法二：哈希 
 
 
1.利用哈希容器 map 降低时间复杂度,遍历数组 nums，i 为当前下标
 2.每个值都判断map中是否存在 target-nums[i] 的 key 值
 3.如果存在则找到了两个值，如果不存在则将当前的 (nums[i],i) 存入 map 中，继续遍历直到找到为止
 
 
 
//正确hash
class Solution1 {
public:
    vector twoSum(vector& nums, int target) {
        vector ans;
        unordered_map mp;
        for(int i=0;i::iterator it=mp.find(key);
            if(it!=mp.end()) {
                ans.push_back(it->second);
                ans.push_back(i);
                return ans;
            }
            mp[nums[i]]=i;
        }
        return ans;
    }
};
 


 
3.关于数组set还是map的选择 
 
 
这道题目中并不需要key有序，选择std::unordered_map 效率更高！
 
 
 


 
4.为什么不能用双指针 
 
 
两数之和不可以用双指针，只能用哈希，而三数之和哈希双指针都可以