代码随想录训练营Day7哈希表Part2|454.四数相加II|383. 赎金信|15. 三数之和|18. 四数之和| 总结

题量越来越大，题目也越来越难了呜呜呜，再加上我对unordered_set和unordered_map这两个数据结构的使用不熟练，需要抽出时间来学习

基础的unordered_set使用

• unordered_set
• 哈希表实现，不保存相同元素，每个元素只保存一次
• 库函数：#include <unordered_set

• unordered_set<int> s;   //定义
  s.insert(x);   //插入，当集合中有该元素，则无效
  s.erase(x);    //删除
  s.size();      //长度
  s.find(x);     //==s.end()时，不存在，通过值查找元素，返回迭代器，
  //若没找到，则返回最后一个元素之后的迭代器s.end()，
  s.count(x);    //查找元素是否存在，==0时，不存在
  s.empyt(x);    //是否为空
  s.clear();     //清空
  
  //迭代器,*it输出元素的值，unordered_set无序，因此输出时元素也无序
  for(auto it = s.begin(); it != s.end(); it++){
      cout<< *it <<" ";
  }
  
  for(auto it : s) cout<<it<<" ";
  
  //通过数组构造集合
  int a[6] = {1,2,3,4,5,6};
  unordered_set<int> s(a,a+6);   //s(a.begin(),a.end());
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20

基础的unordered_map使用

• unordered_map

• 每个key只出现一次，key有对应的value

• unordered_map<int,int> hash;    //要分别定义key和value的两个数据类型
  hash.emplace(key,value);        //插值，当key值存在时无效
  auto it = hash.find(x);         //找到key==x时的位置，返回迭代器
  int value = it->second;         //通过迭代器访问value
  1
  2
  3
  4

454.四数相加II

• 不需要考虑去重，不需要求出具体的数
• 两个数组两个数组的遍历，这样时间复杂度是n方，三个数组遍历是n三方
• 掌握unordered_map用法
• 此题中，重复元素需要计数！！因此要用map结构

383. 赎金信

• 昨天在拓展题目中写过

15. 三数之和

• 一上来只能想到暴力法
• 一层循环，第二层用left和right（这样做的前提：不需要返回下标）
• 哈希法难点在于，三个数不能重复排列组合，并且原数组中可能有重复的数，那就需要手动剔除
• 因此用双指针法。先排序（不需要返回下标），第一个for循环遍历a，剩下的区间用left和right表示b和c，相加后和0相比较，移动left和right。注意需要去重的处理

18.四数之和

• 上一题再套一个for循环
• 有时nums+nums为long long数据型，因此要注意(long long)n1+n2;
• 此处要判断的是target，当target是负数时，不能延续上题的 nums[i]>target 剪枝，而是target > 0 && nums[i] > target