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

Leetcode1

1.问题描述

2.解决方案

解法一：暴力

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

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[j]==target-nums[i]){
                    ans.push_back(i);
                    ans.push_back(j);
                    break;
                }
                
            }
        }
        return ans;
    }
};

解法二：哈希

1.利用哈希容器 map 降低时间复杂度,遍历数组 nums，i 为当前下标
2.每个值都判断map中是否存在 target-nums[i] 的 key 值
3.如果存在则找到了两个值，如果不存在则将当前的 (nums[i],i) 存入 map 中，继续遍历直到找到为止

//正确hash
class Solution1 {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        unordered_map<int,int> mp;
        for(int i=0;i<nums.size();i++){
            int key=target-nums[i];
            unordered_map<int,int>::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.为什么不能用双指针

两数之和不可以用双指针，只能用哈希，而三数之和哈希双指针都可以