leecode-1.俩数之和(map)

题目链接: https://leetcode-cn.com/problems/two-sum/

解题思路:

1.首先的思考必然是暴力解法,复杂度(N2)

2.使用mp容器,由于必存在,所以我的想法是,先将所有出现的数都存入mp,然后用一个for循环,从nums[0]开始查找与之对应的数字target - nums[0]是否存在,如果存在。则进行一个for循环,从i+1寻找该数

 1 vector<int> twoSum(vector<int>& nums, int target) {
 2         unordered_map<int, int> mp;
 3         for (int i = 0; i < nums.size(); i++) {
 4             if (!mp[nums[i]])    mp[nums[i]] = 1;
 5         }
 6        
 7         for (int i = 0; i < nums.size(); i++) {
 8             int temp = target - nums[i];
 9             if (mp[temp]) {
10                 for (int j = i+1; j < nums.size(); j++) {
11                     if (nums[j] == temp)
12                         return {i, j};
13                 }
14             }
15         }
16         return {};
17     }

3.提交之后发现时间空间复杂度也不是非常好,然后查看题解,发现了一个超棒的代码,一次for循环,边查找边存储

 1 vector<int> twoSum(vector<int>& nums, int target) {
 2         unordered_map<int, int> hashtable;
 3         for (int i = 0; i < nums.size(); ++i) {
 4             auto it = hashtable.find(target - nums[i]);
 5             if (it != hashtable.end()) {
 6                 return {it->second, i};
 7             }
 8             hashtable[nums[i]] = i;
 9         }
10         return {};
11     }

 

上一篇:2020.11.24 Leecode刷题 452. 用最少数量的箭引爆气球


下一篇:LeeCode_判定字符是否唯一