C++刷题 – 哈希表

---

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法;

1.两数之和

https://leetcode.cn/problems/two-sum/
一种方法是直接两个for循环暴力求解，时间复杂度为O(N^2)；

另一种解法：使用map记录遍历过的元素

• 每次遍历一个元素，计算其与target的差值，从map中寻找差值，若存在，则返回下标，若不存在，则将遍历完的元素插入map；

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> nums_map; //记录遍历过的元素vector<int> res;for(int i = 0; i < nums.size(); i++){int diff = target - nums[i];if(nums_map.find(diff) != nums_map.end()) // 差值>0且已经遍历{res.push_back(i);res.push_back(nums_map[diff]);break;}else{// diff不在map中，将遍历过的元素插入mapnums_map.insert(make_pair(nums[i], i));}}return res;}
};

2.四数相加II

https://leetcode.cn/problems/4sum-ii/

• 将四个数组分为两组，计算出所有nums1和nums2中每个元素的和，使用map保存结果和个数；
• 然后再遍历nums3和nums4中的元素，计算0 - nums3[i] - nums4[j]的值，结果在map中寻找，如果找到，就在结果中增加相应的个数；

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> sum_map;int count = 0;for(const auto& n1 : nums1) // 保存nums1和nums2中所有对应元素的和与个数{for(const auto& n2 : nums2){sum_map[n1 + n2]++;}}for(const auto& n3 : nums3) // 遍历nums3和nums4，差值在map中寻找{for(const auto& n4 : nums4){int diff = 0 - n3 - n4;if(sum_map.find(diff) != sum_map.end()){count += sum_map[diff];}}}return count;}
};

3.三数之和（重点）

https://leetcode.cn/problems/3sum/description/

• 这道题不适合用哈希法，哈希法可以通过O(N^2)的for循环得到两个数的和，并存放在哈希表中，再通过差值寻找第三个数，但这样会造成重复下标，去重的过程很麻烦；
• 可以使用双指针法
  
• 拿这个nums数组来举例，首先将数组排序，然后有一层for循环，i从下标0的地方开始，同时定一个下标left 定义在i+1的位置上，定义下标right 在数组结尾的位置上。
• 依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。
• 接下来如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
• 如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
  时间复杂度：O(n^2)。
• 最重要的部分其实是去重
• a的去重
  都是和 nums[i]进行比较，是比较它的前一个，还是比较它的后一个。
  如果仅比较后一个：
  
  那我们就把 三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。
  不能有重复的三元组，但三元组内的元素是可以重复的！因此需要和前一个已经遍历过的数据对比；
  
• b与c的去重
  对b和c的去重如果放在找到三元组之前，就会漏掉0，0，0这种情况
  因此left和right的去重应放在找到三元组之后
  如果找到一个三元组后，left右边或者right左边是重复的，那么可以去掉，因为此时三元组有两个数已经确定了，这个三元组就是唯一的，因此重复的left或者right就需要去掉

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;sort(nums.begin(), nums.end()); // 先排序数组//begin从左向右遍历//left和right在begin的右边，计算三者的和，如果小于0，left++，如果大于0，right--//直到找到目标数字或者left和right越界或者相遇for(int begin = 0; begin < nums.size() - 2; begin++){//如果begin > 0，就不需要往后寻找了if(nums[begin] > 0){break;}//begin去重：不能简单地依据nums[begin] == nums[begin + 1]来去重，这样会漏掉-1，-1,2这种情况if(begin > 0 && nums[begin] == nums[begin - 1]){continue;}int left = begin + 1, right = nums.size() - 1;while(left < right){//对left和right的去重如果放在找到三元组之前，就会漏掉0，0,0这种情况int sum = nums[begin] + nums[left] + nums[right];if(sum < 0){left++;}else if(sum > 0){right--;}else{//因此left和right的去重应放在找到三元组之后while(left < right && nums[left] == nums[left + 1]){left++;}while(left < right && nums[right] == nums[right - 1]){right--;}res.push_back(vector<int>{nums[begin], nums[left], nums[right]});//找到之后左右指针同时移动left++;right--;}}}return res;}
};