一道简单题引发的惨案，map完败于unordered_map

题面：

方法：

暴力破解

C++:时间复杂度 O(n2)

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& nums, int target) {
 4         vector<int> ans(2);
 5         int i, j;
 6         for(i=0; i<nums.size(); i++)
 7         {
 8             for(j=i+1; j<nums.size(); j++)
 9             {
10                 if((nums[i]+nums[j]) == target)
11                 {
12                     ans[0] = i;
13                     ans[1] = j;
14                     break;
15                 }
16             }
17         }
18         return ans;
19     }
20 };

 java: 时间复杂度 O(n2)

 1 class Solution {
 2     public int[] twoSum(int[] nums, int target) {
 3         int a[] = new int[2];
 4         int i, j;
 5         for(i=0; i<nums.length; i++)
 6         {
 7             for(j=i+1; j<nums.length; j++)
 8             {
 9                 if((nums[i]+nums[j]) == target)
10                 {
11                     a[0] = i;
12                     a[1] = j;
13                     break;
14                 }
15             }
16         }
17         return a;
18     }
19 }

 

优化算法

java HashMap: 时间复杂度 O(n) hash查找，视为O(1)

 1 class Solution {
 2     public int[] twoSum(int[] nums, int target) {
 3         HashMap<Integer, Integer> map = new HashMap<>();//定义哈希表，用来存储数组中的数字
 4         for(int i=0; i<nums.length; i++)
 5         {
 6             int sub = target - nums[i];
 7             if(map.containsKey(sub))
 8             {
 9                 return new int[] {map.get(sub), i};
10             }
11             map.put(nums[i], i);
12         }
13         throw new IllegalArgumentException("No two sum solution");//异常处理，关键
14     }
15 }

 C++ map：时间复杂度O(n*log(n)) map红黑树查找O(log(n))

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& nums, int target) {
 4         vector<int> res;
 5         map<int, int> mp;
 6         for(int i=0; i<nums.size(); i++)
 7         {
 8             if(mp.find(target - nums[i]) != mp.end())
 9             {
10                 return vector<int> {i, mp[target - nums[i]]};
11             }
12             mp.insert(pair<int, int> {nums[i], i});
13         }
14         return res;
15     }
16 };

C++ unordered_map：时间复杂度O(n)   hash查找O(1)

只需要将👆代码中map改为unordered_map即可大大降低查找复杂度

 1 class Solution {
 2 public:
 3     vector<int> twoSum(vector<int>& nums, int target) {
 4         vector<int> res;
 5         unordered_map<int, int> mp;
 6         for(int i=0; i<nums.size(); i++)
 7         {
 8             if(mp.find(target - nums[i]) != mp.end())
 9             {
10                 return vector<int> {i, mp[target - nums[i]]};
11             }
12             mp.insert(pair<int, int> {nums[i], i});
13         }
14         return res;
15     }
16 };