哈希 | 两数之和

基础铺垫

算法效率

算法效率的评价指标可分为时间复杂度和空间复杂度

• 时间复杂度
  衡量算法的时间效率，即运行速度。

  // 空间复杂度O(N)，若N为常数即为O(1)
  for (size_t i = 0; i < N; i++)
  // 空间复杂度O(N*M)，若第二个循环为N即为O(N^2)
  for (size_t i = 0; i < N; i++)
  	for (size_t i = 0; i < M; i++)
  		;
  

• 空间复杂度
  衡量算法的空间效率，即空间消耗。

Note：随着存储容量的增大，空间复杂度的消耗变得不再重要。通常优先可空间换时间的方式算法改进。

哈希表

• 定义

  unordered_map<key, value> hash_Map; 
  // key, value : int / string / char;
  

• 常见的哈希表操作

  增

  //.insert()函数
  hash_Map.insert(pair<int,int>(key, value));
  // 数组
  hash_Map[key] = value;
  

  删

  // .erase()函数
  hash_Map.erase(key);
  

  改

  // 数组, 改变键对应的值
  hash_Map[key] = new_value;
  // .replace()函数
  hash_Map.replace(old_key now_key, old_value new_value);
  

  查

  // .find()函数, 存在返回键对应的值，不存在返回迭代器hash_Map.end()
  hash_Map.find(key);
  // .count()函数，返回1/0；底层由find()函数实现
  hash_Map.count(key);
  

题目分析

• 题目
  给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
  你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
  你可以按任意顺序返回答案。
• 分析
  给定的数组nums是一个容器，在该题中可以当作一维数组进行处理；
  目标值target是nums中两个元素之和，反过来说就是与两个元素之差为0；
  最终的结果是要返回两个元素对应的下标，即在nums容器中的位置索引；
  返回类型为vector直接{indx1, indx2}的形式进行返回。

解决方案

• 1.暴力枚举 – $O(N^2),O(1)$

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

• 2.哈希表 – $O(N),O(N)$

  class Solution {
  public:
      vector<int> twoSum(vector<int>& nums, int target) {
          unordered_map<int, int> hash_Map;
          for(int i = 0; i < nums.size(); i++)
          {
              int temp = target - nums[i];
              //if(hash_Map.count(temp))		// count()的底层依靠find()实现, 相对而言会更慢.
              if(hash_Map.find(temp) != hash_Map.end()) // 
              {
                  return {hash_Map[temp], i};
              }
              hash_Map[nums[i]] = i;
          }
          return {};
  
      }
  };