LeetCode刷题记录（第二天）1. 两数之和

题目：1. 两数之和

标签：数组 哈希表
题目信息：

思路一：暴力做法

直接两重for循环遍历，判断两数和为target的时候返回下标结果

代码实现：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        vector<int>ans;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(nums[i]+nums[j] == target){
                    ans.push_back(i);
                    ans.push_back(j);
                    return ans;
                }
            }
        }
        return ans;
    }
};

时间复杂度分析：
O(n^2)

思路二：哈希表

用哈希表来记录值和对应的下标。
先新建一个哈希表map
遍历数组，每遍历一个值，就判断（target-这个值）在不在map中，如果在，就可以结束遍历了。
否则，将这个值和对应下标存入哈希表中，遍历继续。

代码实现：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        vector<int>ans;
        unordered_map<int,int>mp;//值，下标
        for(int i=0;i<n;i++){
            if(mp.find(target-nums[i])!=mp.end()){
                ans.push_back(i);
                ans.push_back(mp[target-nums[i]]);
            }
            mp[nums[i]]=i;
            
        }
        return ans;
    }
};

时间复杂度分析：
O(1)

总结：

哈希表的妙用还是太多啦。