代码随想录算法训练营第七天|哈希表-part2
1. LeetCode 454. 四数相加 II
题目
思路
- 无
刷随想录后想法
- 将四数相加转化为两数之和
- 借用
unordered_map，利用两数之和思想解决本问题实现困难
- 代码尚模糊，不过整个流程能写出来
- 对部分C++特性尚不清楚，比如
map的使用实现代码
class Solution { public: int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) { unordered_map <int, int> uMap; int count = 0; for(int a:nums1){ for(int b:nums2){ uMap[a+b]++; } } for (int c:nums3){ for (int d:nums4){ if(uMap.find(0-(c+d)) != uMap.end()){ //如果找到相反数了 count += uMap[0-(c+d)]; } } } return count; } };学习收获
- 四数变两数，有繁化简的思想
2. LeetCode 383. 赎金信
题目
思路
- 使用
map，其中的key为magazine里面的每一个字符，value为每个字符的个数，如果个数为0则返回false刷随想录后想法
- 用
map消耗过大，因为都是小写字母，用数组完全ok实现困难
实现代码
class Solution { public: bool canConstruct(string ransomNote, string magazine) { int hash[26] = {0}; for (int i=0; i < magazine.size(); i++){ hash[ magazine[i]- 'a']++; } for (int i=0; i < ransomNote.size(); i++){ if(hash[ ransomNote[i] - 'a'] <= 0){ return false; }else{ hash[ ransomNote[i] - 'a' ]--; } } return true; } };学习收获
- 同类问题相同解法
- 使用
map使用数组的时机
3. LeetCode 15. 三数之和
题目
思路
- 无
刷随想录后想法
- 排序+双指针
实现困难
- 总是将题目条件看漏，导致思考问题想象的过于复杂
- 自己编写时，对判重条件总是会漏掉一些，思维不够全面和严谨
实现代码
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector< vector<int> > result; //先进行排序 sort(nums.begin(), nums.end()); for (int i=0; i < nums.size(); i++){ int left = i+1; int right = nums.size()-1; //如果i>0,则后续所有都是>0的数，因此直接跳出循环 if (nums[i] > 0){ break; } //如果i在前面一个有一样的，就不用重复判断了 if ( i > 0 && nums[i] == nums[i-1] ){ continue; } //如果i<=0 while( left < right ){ if((nums[i] + nums[left] + nums[right]) == 0){ //如果和为0，则找到了一组 result.push_back(vector<int> {nums[i], nums[left], nums[right]}); //这里注意去重 1111，只有一个1有效 while(right > left && nums[right] == nums[right-1]) right--; while(left < right && nums[left] == nums[left+1]) left++; //别忘记了左右指针移动 right--; left++; }else if((nums[i] + nums[left] + nums[right]) > 0){ right--; }else{ left++; } } } return result; } };学习收获
- 并不是所有的题目用哈希法都简单，尝试思考对指针的运用
4.Leecode 18. 四数之和
题目
思路
- 参考前面三数之和的思想，用三指针
刷随想录后想法
- 更改思路，两个基数，两个依旧用双指针
- 注意
target可能是负数，-1+(-2) = -3，因此剪枝时要主语与三树之和的区别- 剪枝要仔细
实现困难
- 容易漏掉剪枝条件，或者说错判剪枝条件
- 没考虑到溢出情况
实现代码
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; sort(nums.begin(), nums.end()); for (int k = 0; k < nums.size(); k++){ //第一层剪枝，注意包含target=0的情况 if (nums[k] > target && target >= 0){ break; } //存在k和k-1一样的情况，需要去掉 if (k > 0 && nums[k] == nums[k - 1]){ continue; } for(int i = k+1; i < nums.size(); i++){ //第二层剪枝 if( (nums[k] + nums[i]) > target && target >= 0){ break; } //注意这里是i>k+1 而不是i>0 if(i > k + 1 && nums[i] == nums[i - 1]){ continue; } int left = i + 1; int right = nums.size() - 1; while(left < right){ //这里要用(long)，为什么？ if((long)nums[k] + nums[i] + nums[left] + nums[right] > target){ right--; }else if ((long)nums[k] + nums[i] + nums[left] + nums[right] < target){ left++; }else{ // 四数之和为target result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]}); //去掉right和left身前一样的 while(right > left && nums[right] == nums[right-1]){ right--; } while(left < right && nums[left] == nums[left+1]){ left++; } right--; left++; } } } } return result; } };学习收获
- 双指针思想，同类问题转化为“三数之和”
- 双指针的广泛应用