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)

总结：

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