专业网站制作公司招聘,网络优化网站 s,电子购物网站开发,做网站教程第一课想编写这一版#xff0c;是因为之前复习字符串或者双指针等其他栏目时候没有写文章#xff0c;但是现在回过头来刷#xff0c;所以想着写一篇#xff0c;我在leetcode的收藏夹里收藏了一些我自认为需要多加练习的题目#xff0c;它们并非是很难的#xff0c;极不易理解的…想编写这一版是因为之前复习字符串或者双指针等其他栏目时候没有写文章但是现在回过头来刷所以想着写一篇我在leetcode的收藏夹里收藏了一些我自认为需要多加练习的题目它们并非是很难的极不易理解的题目而是对于我来说题目简单但是却不好写代码的、代码需要注意的细节多的和非常规思路的。这些题并不都是很难但有些需要技巧 209.长度最小的子数组
209. 长度最小的子数组 - 力扣LeetCodehttps://leetcode.cn/problems/minimum-size-subarray-sum/?envTypelistenvIdZCa7r67M这道题并不是所谓真正意义上的难题而是我为了警示自己要认真读题这道题一开始做的时候我把大于等于target这一重要的解题关键信息粗略的看成了等于target做完了之后自然是没有ac去看了官方题解发现很不可思议甚至觉得是测试用例出错了相信大家也遇到过和我类似的情况吧认真读题是关键
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int left0;int mincountINT_MAX;int sum0;for(int i0;inums.size();i){sumnums[i];while(sumtarget){mincountmin(mincount,i-left1);//先做统计sum-nums[left];left;}}return mincountINT_MAX?0:mincount; }
};
为数不多我觉得需要注意的细节是使用while循环缩小窗口而非if语句这是因为如果遇上了前几个数很小当前数字很大的情况这时需要很快的情况窗口找答案如果你用if去判断看上去没什么问题但是如果数组长度很小你很容易找不到正确的答案i就已经走到数组末尾了也就是右窗口遍历的太快了以至于虽然后面可能含有答案你也拿不到了
还有一个注意的点是计数器mincount先做统计再进行缩小窗口不然也可以做出来就是比较时候麻烦些而已。顺便说一下也可以不让右窗口一直移到这样就不用考虑这些每次先判断窗口和与target比较不过这样代码显得不够整洁 454.四数相加II
454. 四数相加 II - 力扣LeetCodehttps://leetcode.cn/problems/4sum-ii/?envTypelistenvIdZCa7r67M这道题是有技巧的不过也相对其他题简单一些解题思路是两个数组为一组进行相加把和录到哈希表map里这里的键记录的是两个数相加的和值记录的是这个和出现的次数前两个数组和入到哈希表以后再用0-另两个数组和看看能不能在map里找到。如果能则使resmap【0-sum】 为什么是 之前我的想法是每找到一次map对应的位置值-- 但是是不对的因为我们并不是重复计算了那个数字的个数而是两数组的各个位置和都算了一遍如果自减了就很可能导致遍历第三四数组查找那个位置时本次查找减没了而下一次查找时候要用时候没有了 这里的道理和前两个数组相加求值需要累加道理是一样的不同的位置加出来的和肯定是下标不会重复的 去自行模拟一下【-1-1】、【-11】、【-11】、【1-1】 便可以知道 15.三数之和
15. 三数之和 - 力扣LeetCodehttps://leetcode.cn/problems/3sum/?envTypelistenvIdZCa7r67M看起来和上一道题是一样的题一样的思路其实不然这道题其实不适合纯哈希表解决反正我只用哈希表现在是超时的
并且仔细看题目可以知道上一道题是在四个数组里找和是target的这道题是在一个数组里找三个数它们的和等于0看着差不多但是不同的是三数之和需要对三元组进行去重去重的需要使得使用哈希表变得十分困难。我们要在加法循环里使用set哈希辅助完成数据的存储然后判断第二个数字去重则更为麻烦
思路简单的来说是外层循环遍历第一个数里层用set来避免元素重复使用这次使用5这个数字和上次也使用5这个数字得到的结果是重复的那如何判断呢就是要排序并不仅仅是jinums【j-1】nums【j】这样就去重了比如说【0000】这个数据我们i第一次遍历到第一个数里层循环遍历第二个数字而我们此时在哈希表里找有没有第三个数字相加得到0显然是找不到的因为我们还没有开始放数在哈希表然后进行j走到第三个0这个时候直接判断那步排重直接就跳出循环了这是错误的。
并且放哈希表的数不是0-当前两个数字的和而是放入当前第二个数遍历的数字这也是当时很让我费解的为什么不放入0-前两个数字的和也不放入第三个数而是选择放入第二个呢这是因为0-前两个数和在整个数组不一定能找得到这不是存在的数不能放进去而第三个数字要想取得是要再写循环的这就失去了写哈希表的意义也增大了时间复杂度
总的来说在面试时用哈希很难写出题解要注意很多细节和剪枝稍不留神就超时了细节尤其是第二个数字的重复判断我觉得不知道这个特殊测试用例的话是很难想到bug出在哪里的
ok说了这么多我们来看看推荐的写法是什么推荐的写法应该是排序和双指针的搭配解法同样也需要排序记住大多数的需要去重的时候都需要对数据排序。排序后外层循环遍历第一个数里层循环是双指针一个指针☞i的下一个数字另一个☞数组最后一个数字因为已经排好序了所以如果当前三个数加起来过大就使右指针向左移反之左指针向右移。
这里排序起到了两个作用一是使去重变得简单二是使数据有规律后双指针能够调节使答案更容易被找到
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(),nums.end());int sum0;vectorvectorintres;int left0,right0;if(nums[0]0)return res;for(int i0;inums.size();i){if(i0nums[i]nums[i-1])continue;int slowi1,fastnums.size()-1;while(slowfast){if(slowi1nums[slow]nums[slow-1]){slow;continue;}if(fast1nums.size()nums[fast]nums[fast1]){fast--;continue;}if(nums[i]nums[slow]nums[fast]0){res.push_back({nums[i],nums[slow],nums[fast]});slow,fast--;}else if(nums[i]nums[slow]nums[fast]0)fast--;else slow;}}return res;}
};18.四数之和
18. 四数之和 - 力扣LeetCodehttps://leetcode.cn/problems/4sum/?envTypelistenvIdZCa7r67M四数之和要比四数之和II是难一点的不过思路也是类似三数之和的可以说上一道题知道思路这一道题也可以很容易的解出来。
也是排序去重双指针解法不同的是由于是四个数的和所以外层是双for循环然后里面还是双指针的思路直接看代码
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {sort(nums.begin(),nums.end());vectorvectorintres;for(int i0;inums.size();i){if(i0nums[i]nums[i-1])continue;for(int ji1;jnums.size();j){if(ji1nums[j]nums[j-1])continue;int leftj1,rightnums.size()-1;while(leftright){if((long)nums[i]nums[j]nums[left]nums[right]target){res.push_back({nums[i],nums[j],nums[left],nums[right]});left,right--;while(leftrightnums[left]nums[left-1])left;while(leftrightnums[right]nums[right1])right--;}else if((long)nums[i]nums[j]nums[left]nums[right]target)right--;else left;}}}return res;}
};
这个代码和上一道题的双指针循环里判断两个指针去重又有一些不同但是思路是一样的这道题的排重思路是如果此时找到了答案那就直接进入先放到res数组里然后去重保证下一次找到的答案绝对不会重复采用循环去重是正确的选择因为可能连续几个答案都一样。
那为什么上一道题使用的是if呢这能去重干净吗
仔细看它的去重是一进来就排重而且排重完毕后continue再判断一次直到相邻不再重复这其实和while是一样的效果只是两种表达方式。
这道题是不能和四数之和II去类比的应该和上一道题三数之和去比较都不适合用哈希同样的官方题解也并未给出哈希解法 以上便是这一期的全部内容下一期同样也是不容易解的专题
都看到这里了如果有用的话别忘了一键三连哦如果是互粉回访我也会做的
大家有什么想看的题解或者想看的算法专栏、数据结构专栏可以去看看往期的文章有想看的新题目或者专栏也可以评论区写出来讨论一番本账号将持续更新。 期待您的关注
