[数据结构与算法]leetcode-1.两数之和

题目内容

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

题解

个人题解：

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

优化题解：

方法一：暴力枚举

• 思路及算法：
  最容易想到的方法是枚举数组中的每一个数 x，寻找数组中是否存在 target - x。
  当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。

• 代码:

  class Solution {
  public:
      vector<int> twoSum(vector<int>& nums, int target) {
          int n = nums.size();
          for (int i = 0; i < n; ++i) {
              for (int j = i + 1; j < n; ++j) {
                  if (nums[i] + nums[j] == target) {
                      return {i, j}; //可以直接返回这样一个数组，不需要用到vector
                  }
              }
          }
          return {}; //没有找到的话，返回空数组
      }
  };
  

• 复杂度分析
  时间复杂度：O(N^2)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
  空间复杂度：O(1)。

方法二：哈希表

• 思路及算法
  注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
  使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)降低到 O(1)。
  这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

• 代码

  class Solution {
  public:
      vector<int> twoSum(vector<int>& nums, int target) {
          unordered_map<int, int> hashtable; //创建哈希表
          for (int i = 0; i < nums.size(); ++i) {
              auto it = hashtable.find(target - nums[i]); //在当前哈希表中找target-num[i]
              if (it != hashtable.end()) {
               	//如果能找到，则返回迭代器的second值，在这里就是索引；以及当前循环的索引i
                  return {it->second, i};
              }
              hashtable[nums[i]] = i; //如果找不到，则把本次循环的nums[i]插入哈希表中
          }
          return {};
      }
  };
  

• 复杂度分析
  时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
  空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。

相关知识点

哈希表

• 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
• 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
• 若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。
• unordered_map是c++ 哈希表的实现模板，在头文件<unordered_map>中，存储key-value的组合，unordered_map可以在常数时间内，根据key来取到value值。
• unordered_map记录元素的hash值，根据hash值判断元素是否相同。map相当于java中的TreeMap，unordered_map相当于HashMap。无论从查找、插入上来说，unordered_map的效率都优于hash_map，更优于map；而空间复杂度方面，hash_map最低，unordered_map次之，map最大。
• unordered_map与map的对比
  存储时是根据key的hash值判断元素是否相同，即unordered_map内部元素是无序的，而map中的元素是按照二叉搜索树存储（用红黑树实现），进行中序遍历会得到有序遍历。所以使用时map的key需要定义operator<。而unordered_map需要定义hash_value函数并且重载operator==。但是很多系统内置的数据类型都自带这些。
• unordered_map的成员函数
  • 迭代器
    begin 　 返回指向容器起始位置的迭代器（iterator）
    end 　　 返回指向容器末尾位置的迭代器
    cbegin　 返回指向容器起始位置的常迭代器（const_iterator）
    cend 　　返回指向容器末尾位置的常迭代器
    元素的键值分别是迭代器的first和second属性。使用(*it).first或者it->first获取。
  • 容量
    size 　　 返回有效元素个数
    max_size 返回 unordered_map 支持的最大元素个数
    empty 判断是否为空
  • 元素插入与删除
    insert 　　插入元素
    erase　　 删除元素 ，可以通过迭代器或者key进行删除
    clear　　 清空内容
    swap 　　 交换内容

    unordered_map<int,int> mymap;
    //插入
    mymap.insert({1,0});//数组插入
    mymap[1] = 0;//键值插入
    mymap.insert(mymap2.begin(),mymap2.end());//插入另一个哈希表中的元素
    mymap.insert(pair<int,int>(0,1));
     
    //删除
    mymap.erase(mymap.begin()); 
    mymap.erase(1);
    mymap.clear();
    

  • 查找
    find 　　　　　　通过给定主键查找元素,没找到：返回unordered_map::end
    count 　　　　　返回匹配给定主键的元素的个数
    equal_range 　　返回值匹配给定搜索值的元素组成的范围

    if (mymap.find(0) != mymap.end())
        cout << "found" << endl;
    else
    	cout << "not found" << endl;