企业购 网站建设,诸城易讯网站建设服务中心,深圳找网站建设公司哪家好,搜索风云榜百度C刷题 – 哈希表 文章目录 C刷题 -- 哈希表1.两数之和2.四数相加II3.三数之和#xff08;重点#xff09; 当我们需要查询一个元素是否出现过#xff0c;或者一个元素是否在集合里的时候#xff0c;就要第一时间想到哈希法;
1.两数之和
https://leetcode.cn/problems/two…C刷题 – 哈希表 文章目录 C刷题 -- 哈希表1.两数之和2.四数相加II3.三数之和重点 当我们需要查询一个元素是否出现过或者一个元素是否在集合里的时候就要第一时间想到哈希法;
1.两数之和
https://leetcode.cn/problems/two-sum/ 一种方法是直接两个for循环暴力求解时间复杂度为O(N^2)
另一种解法使用map记录遍历过的元素
每次遍历一个元素计算其与target的差值从map中寻找差值若存在则返回下标若不存在则将遍历完的元素插入map
class Solution {
public:vectorint twoSum(vectorint nums, int target) {unordered_mapint, int nums_map; //记录遍历过的元素vectorint 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(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {unordered_mapint, 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 定义在i1的位置上定义下标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的去重如果放在找到三元组之前就会漏掉000这种情况 因此left和right的去重应放在找到三元组之后 如果找到一个三元组后left右边或者right左边是重复的那么可以去掉因为此时三元组有两个数已经确定了这个三元组就是唯一的因此重复的left或者right就需要去掉
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint res;sort(nums.begin(), nums.end()); // 先排序数组//begin从左向右遍历//left和right在begin的右边计算三者的和如果小于0left如果大于0right--//直到找到目标数字或者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的去重如果放在找到三元组之前就会漏掉00,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(vectorint{nums[begin], nums[left], nums[right]});//找到之后左右指针同时移动left;right--;}}}return res;}
};
