汕头站扩建什么时候完成,服务器租用国外,上海企业公示信息填报,wordpress获取文章发表时间目录
一、454. 四数相加 II
二、383. 赎金信
三、15. 三数之和18. 四数之和 一、454. 四数相加 II
题目链接#xff1a;力扣
文章讲解#xff1a;代码随想录
视频讲解#xff1a; 学透哈希表#xff0c;map使用有技巧#xff01;LeetCode#xff1a;454.四数相加II…目录
一、454. 四数相加 II
二、383. 赎金信
三、15. 三数之和18. 四数之和 一、454. 四数相加 II
题目链接力扣
文章讲解代码随想录
视频讲解 学透哈希表map使用有技巧LeetCode454.四数相加II
题目
给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足
0 i, j, k, l n nums1[i] nums2[j] nums3[k] nums4[l] 0
代码
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {unordered_mapint,int map;int ans0;/*for(int i0;inums1.size();i)//两组合一{for(int j0;jnums1.size();j){map[nums1[i]nums2[j]];}}for(int i0;inums1.size();i)//两组合一{for(int j0;jnums1.size();j){// if(map.find(-(nums3[i]nums4[j])) ! map.end())//hash查询增加时间ans map[-(nums3[i]nums4[j])];//默认构造0}}*/for(int i:nums1)//指针速度更快for(int j:nums2)map[i j];for(int i:nums3)for(int j:nums4)//if(map.find(-(ij)) ! map.end())//hash查询增加时间ans map[-(ij)];//默认构造0return ans;}
};
//用哈希数组替代map减去哈希计算的时间。
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {sort(nums1.begin(), nums1.end());sort(nums2.begin(), nums2.end());sort(nums3.begin(), nums3.end());sort(nums4.begin(), nums4.end());int n nums1.size();int low min(nums1[0]nums2[0], -nums3[n-1]-nums4[n-1]);int high max(nums1[n-1]nums2[n-1], -nums3[0]-nums4[0]);int range high - low 1;vectorint hash(range, 0);int ans 0;for(int i 0; i n; i)for(int j 0; j n; j)hash[nums1[i]nums2[j] - low];for(int i 0; i n; i)for(int j 0; j n; j){int find -nums3[i]-nums4[j]-low;if (hash[find] ! 0)ans hash[find];}return ans;}
};
时间复杂度: O(n^2) 空间复杂度: O(n^2)
⏲8:52
总结1.将map当数组用其下标相当于key数组的值则为value。2.若访问map中不存在的值就会构造一对key和value且value为0。3.循环用指针的速度大于变量。4.形如x1x2....k可变成x1k-x2-x3... 方便查找。
二、383. 赎金信
题目链接力扣
文章讲解代码随想录
视频讲解
题目给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以返回 true 否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。代码
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int hash[26] {0};for(auto i : ransomNote)hash[i-a];for(auto i : magazine)hash[i-a]--;for(int i 0; i 26; i)if (hash[i] 0) return false;return true;}
};
时间复杂度: O(n) 空间复杂度: O(1)
⏲2:26
三、15. 三数之和18. 四数之和
15题目链接力扣
18题目链接力扣
文章讲解代码随想录
视频讲解梦破碎的地方| LeetCode15.三数之和
题目
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。
代码
三数之和
class Solution {
public:vectorvectorint threeSum(vectorint nums) {
//哈希/*sort(nums.begin(), nums.end());vectorvectorint ans;int size nums.size();for(int i 0;i nums.size(); i){if (nums[i]0) break;if (i0 nums[i] nums[i-1]) continue;unordered_setint set;for (int j i1; j nums.size(); j) {if (j i2 nums[j] nums[j-1] nums[j-1] nums[j-2]) continue;int t -(nums[i] nums[j]);if (set.find(t) ! set.end()) {ans.push_back({nums[i], nums[j], t});set.erase(t);} else set.insert(nums[j]);}}return ans;*/
//双指针sort(nums.begin(), nums.end());vectorvectorint ans;int size nums.size();for(int i 0; i size-2; i){if (i0 nums[i] nums[i-1]) continue;for(int left i1, right size-1; leftright;){int sum nums[i] nums[left] nums[right];if (sum0) right--;else if(sum0) left;else{ans.push_back({nums[i],nums[left],nums[right]});while(left right nums[left]nums[left1]) left;while(left right nums[right]nums[right-1]) right--;right--;left;}}}return ans;}
};
四数之和
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint ans;if (nums.size() 4) return ans;sort(nums.begin(), nums.end());for (int k 0; k nums.size() - 3; k) {if (k 0 nums[k] nums[k-1]) continue; if ((long)nums[k] nums[k1] nums[k2] nums[k3] target) break; if ((long)nums[k] nums[nums.size()-3] nums[nums.size()-2] nums[nums.size()-1] target) continue; for (int i k1; i nums.size()-2; i) {if (i k1 nums[i] nums[i-1]) continue; int left i1, right nums.size()-1;while (right left) {long sum (long)nums[k] nums[i] nums[left] nums[right];if (sum target) right--;else if (sum target) left;else {ans.push_back({nums[k], nums[i], nums[left], nums[right]});while (right left nums[right] nums[right - 1]) right--; while (right left nums[left] nums[left 1]) left; right--; left;}}}}return ans;}
};总结1.剪枝根据第一个数考虑后续相应数不可能成立的情况。2.去重与前一个数比较是否相同可以保障已经走过一遍且第一个数的重复数的后续数的所有情况被包含于第一个数的前数中。中间原理相同。最后双指针部分在保障已经有一次的情况下走完以避免直接退出循环。3.时间复杂度双指针降低一阶。双向指针可以快速跳过左右重复或差值过大的数。
哈希与双指针的适用
哈希法不要求去重(去重繁琐) 或 要求返回元素下标双指针需要排序双指针法要求去重 且 不要求返回元素下标
