网站建设要不要学编码,网站的内容与功能设计,有没有教做蛋糕的网站,建站工具免费文章目录 454.四数相加II思路C代码 383.赎金信C 代码 15. 三数之和排序哈希法思路C代码 排序双指针法思路去重C代码 18.四数之和前言剪枝C代码 454.四数相加II 力扣题目链接 文章链接#xff1a;454.四数相加II 视频链接#xff1a;学透哈希表#xff0c;map使用有技巧… 文章目录 454.四数相加II思路C代码 383.赎金信C 代码 15. 三数之和排序哈希法思路C代码 排序双指针法思路去重C代码 18.四数之和前言剪枝C代码 454.四数相加II 力扣题目链接 文章链接454.四数相加II 视频链接学透哈希表map使用有技巧LeetCode454.四数相加II 状态磕磕碰碰本题的重点在于如何构建哈希表如何构建查询集 思路
画个图分别四个整数数组长度一致。我们先前做过关于两数之和的题目很难不考虑一个类似的解法。本题的核心就是分别从四个数组中抽四个元素计算有多少个和为0的元组
对于下面这个核心问题
判断一个元素是否出现在集合中这样的题目非常适合用哈希表。如果没有集合呢那就构造一个集合再进行比较
集合的构造构造一个存储ab的map集合其中key a bvalue a b出现的次数。这样后序查找的时候就能知道cd对应的ab有多少个了查询集元素查询集就是bc在对集合中元素查询的时候我们应该用0 - (b c)。并且需要注意的是每一对bc都可能有各自对应的ab所以记得设计一个统计次数的变量。伪代码
for (int a : A)
{for (int b : B){unordered_map[a b]; }
}
count 0//记录结果
for (int c : C)
{for (int d : D){if (map.find(0 - (c d)) ! map.end())count map(0 - (c d))}
}
return countC代码
class Solution {
public:int fourSumCount(vectorint A, vectorint B, vectorint C, vectorint D) {unordered_mapint, int umap; //key:ab的数值value:ab数值出现的次数// 遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中for (int a : A) {for (int b : B) {umap[a b];}}int count 0; // 统计abcd 0 出现的次数// 在遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话就把map中key对应的value也就是出现次数统计出来。for (int c : C) {for (int d : D) {if (umap.find(0 - (c d)) ! umap.end()) {count umap[0 - (c d)];}}}return count;}
};383.赎金信 力扣题目链接 文章链接383.赎金信 视频链接无 状态较简单很像242.有效的字母异位词 这道题目和242.有效的字母异位词 很像242.有效的字母异位词 相当于求 字符串a 和 字符串b 是否可以相互组成 而这道题目是求 字符串a能否组成字符串b而不用管字符串b 能不能组成字符串a。
本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成但是这里需要注意两点。
第一点“为了不暴露赎金信字迹要从杂志上搜索各个需要的字母组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母这一点很重要
C 代码
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int record[26] {0};//addif (ransomNote.size() magazine.size()) {return false;}for (int i 0; i magazine.length(); i) {// 通过record数据记录 magazine里各个字符出现次数record[magazine[i]-a] ;}for (int j 0; j ransomNote.length(); j) {// 遍历ransomNote在record里对应的字符个数做--操作record[ransomNote[j]-a]--;// 如果小于零说明ransomNote里出现的字符magazine没有if(record[ransomNote[j]-a] 0) {return false;}}return true;}
};15. 三数之和 力扣题目链接 文章链接15. 三数之和 视频链接梦破碎的地方| LeetCode15.三数之和 状态对于不能重复的要求去重逻辑相当重要为了后续去重逻辑的方便一定要记得排序 排序哈希法
思路
两层for循环就可以确定 a 和b 的数值了可以使用哈希法来确定 0-(ab) 是否在哈希表里出现过其实这个思路是正确的但是我们有一个非常棘手的问题就是题目中说的不可以包含重复的三元组。
把符合条件的三元组放进vector中然后再去重这样是非常费时的很容易超时也是这道题目通过率如此之低的根源所在。
并且在哈希法中处理重复元素相当复杂
C代码
代码流程 ⭐️注意第一个for循环其实就是固定a第二个for循环其实是在处理b和c所以b需要连续三个元素相同才会跳过unordered_setint set;一定记得写到循环体内因为只有固定好了a才能设置不然a的固定和去重就失去意义了
排序首先数组被排序。这是为了便于后续的去重逻辑和判断。外层循环遍历每个元素作为a对于数组中的每个元素 nums[i]它被视为三元组的第一个元素 a。提前结束的条件如果在排序后的数组中当前的元素 a 已经大于0那么不可能找到 a b c 0 的组合了因为数组是有序的后面的元素都会大于等于 a。去重逻辑 for a为了避免在结果集中出现重复的三元组如果当前元素与前一个元素相同就跳过这个元素因为它作为 a 时对应的所有三元组已经在之前被找出。内层循环寻找b和c对于每个固定的 a使用一个循环来遍历 a 之后的所有元素视它们为三元组的第二个元素 b。同时使用一个哈希集合unordered_set来帮助查找第三个元素 c。去重逻辑 for b在寻找 b 的过程中如果当前元素与它前面的两个元素都相同则跳过当前元素这是为了防止 b 重复。注意这里跳过的条件是当前元素和它前面的两个元素相同这个逻辑保证了至少有两个相同的 b 值时才会跳过避免了错误地跳过有效的三元组组合。
为什么要求当前元素与它前面的两个元素都相同才跳过当前元素。举个例子就懂了[-2, 0, 1, 1, 2]。正确答案是[-2, 2, 0]和[-2, 1, 1]。如果只与前面一个元素相同那么[2-, 1, 1]这个答案就会被漏掉。这是因为b,c完全是可以相等的。所以说如果连续两个元素紧挨在一起必须要执行后续对于C的查询。
寻找c通过计算 c 0 - (a b)并在哈希集合中查找是否存在这样的 c。如果存在则将 (a, b, c) 作为一个结果三元组加入到结果列表中。去重逻辑 for c一旦找到有效的三元组并将其加入结果列表后立即从哈希集合中删除 c这样做是为了避免在相同的 a 和 b 值下找到重复的 c。
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint result;sort(nums.begin(), nums.end());// 找出a b c 0// a nums[i], b nums[j], c -(a b)for (int i 0; i nums.size(); i) {// 排序之后如果第一个元素已经大于零那么不可能凑成三元组if (nums[i] 0) {break;}if (i 0 nums[i] nums[i - 1]) { //三元组元素a去重continue;}unordered_setint set;for (int j i 1; j nums.size(); j) {if (j i 2 nums[j] nums[j-1]) { // 三元组元素b去重continue;}int c 0 - (nums[i] nums[j]);if (set.find(c) ! set.end()) {result.push_back({nums[i], nums[j], c});set.erase(c);// 三元组元素c去重} else {set.insert(nums[j]);}}}return result;}
};排序双指针法
思路
还是必须得排序不然去重逻辑根本写不出来。
双指针的思路就相当简单了。举例说明
假设数组nums [-2, -1, 0, 1, 2, 3] 我们一个for循环控制i(index0)从第一个元素开始往后遍历。a就是nums[i]。b就是这个数组left指向的数值(index1)c是数组right指向的数值(indexnums.size())。 如果num[i]nums[left]nums[right]0.是不是说明三个数太大了那么我们就要缩小这三个数但是由于a已经是固定的了。我们如何让三个数减小呢就让right往里移所以我们一定要讲数组进行排序这样right往里移一位才缩小了三数之和。 如果num[i]nums[left]nums[right]0.是不是说明三个数太小了我们要把这三个数和变大所以我们就把left往后移动。
如果num[i]nums[left]nums[right]0。说明我们收获结果结果就分别是nums[i]、nums[left]、nums[right]存放在二维数组result中。
去重
双指针法的去重逻辑非常简单。
外循环的去重与哈希法逻辑一样不能连续两个相等。
if (i 0 nums[i] nums[i - 1]) {continue;
}内循环的去重即b、c的去重。如果数组是[-2, -1, -1, -1, 1, 1, 1]。那么我们只能等left取完-1并且right取完1之后进行去重也就是nums[left]!nums[left]同时还要满足nums[right-- ]! nums[left]
// 去重逻辑应该放在找到一个三元组之后对b 和 c去重
while (right left nums[right] nums[right - 1]) right--;
while (right left nums[left] nums[left 1]) left;C代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint result;sort(nums.begin(), nums.end());// 找出a b c 0// a nums[i], b nums[left], c nums[right]for (int i 0; i nums.size(); i) {// 排序之后如果第一个元素已经大于零那么无论如何组合都不可能凑成三元组直接返回结果就可以了if (nums[i] 0) {return result;}// 错误去重a方法将会漏掉-1,-1,2 这种情况/*if (nums[i] nums[i 1]) {continue;}*/// 正确去重a方法if (i 0 nums[i] nums[i - 1]) {continue;}int left i 1;int right nums.size() - 1;while (right left) {// 去重复逻辑如果放在这里000 的情况可能直接导致 rightleft 了从而漏掉了 0,0,0 这种三元组/*while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;*/if (nums[i] nums[left] nums[right] 0) right--;else if (nums[i] nums[left] nums[right] 0) left;else {result.push_back(vectorint{nums[i], nums[left], nums[right]});// 去重逻辑应该放在找到一个三元组之后对b 和 c去重while (right left nums[right] nums[right - 1]) right--;while (right left nums[left] nums[left 1]) left;// 找到答案时双指针同时收缩right--;left;}}}return result;}
};18.四数之和 力扣题目链接 文章链接第18题. 四数之和 视频链接难在去重和剪枝| LeetCode18. 四数之和 状态被三数之和难倒后四数之和直接看答案了不好的习惯。 前言
还记得四数相加II吗建议去复习一下两个题目的不同点。想一想为什么四数之和要更难。
还记得三数之和吗方法上面有一些什么区别
其实和三数之和本质上是一样一样的。只不过我们在三数一和外面再套上一层循环罢了这样可以想出代码逻辑。如下所述[-2, 0, 1, 2, 3]定义:
k 从index 0开始;
i从index 1开始;
那么left从index 2right从index nums.size()开始如下图所示 方框中直接套三数之和的代码。
但是这里有两个主要细节和难点。
剪枝
第一个循环是对k那么如何对k进行剪枝呢
if(nums[k] target) break;这样剪枝是错误的因为后面的**i、left、right**都可能是负数那么nums[k]大于target不能进行剪枝if(nums[k] target nums[k] 0);这样的剪枝才是正确的。
第二个循环是对n也就是代码的二级剪枝
if (nums[k] nums[i] target nums[k] nums[i] 0) {break;
}//或者
//只要 nums[k] nums[i] target那么 nums[i] 后面的数都是正数的话就一定 不符合条件了
if (nums[k] nums[i] target nums[i] 0) {break;
}C代码
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint result;sort(nums.begin(), nums.end());for (int k 0; k nums.size(); k) {// 剪枝处理if (nums[k] target nums[k] 0) {break; // 这里使用break统一通过最后的return返回}// 对nums[k]去重if (k 0 nums[k] nums[k - 1]) {continue;}for (int i k 1; i nums.size(); i) {// 2级剪枝处理if (nums[k] nums[i] target nums[k] nums[i] 0) {break;}// 对nums[i]去重if (i k 1 nums[i] nums[i - 1]) {continue;}int left i 1;int right nums.size() - 1;while (right left) {// nums[k] nums[i] nums[left] nums[right] target 会溢出if ((long) nums[k] nums[i] nums[left] nums[right] target) {right--;// nums[k] nums[i] nums[left] nums[right] target 会溢出} else if ((long) nums[k] nums[i] nums[left] nums[right] target) {left;} else {result.push_back(vectorint{nums[k], nums[i], nums[left], nums[right]});// 对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 result;}
};
