不容易解的题9.26

想编写这一版，是因为之前复习字符串或者双指针等其他栏目时候没有写文章，但是现在回过头来刷，所以想着写一篇，我在leetcode的收藏夹里收藏了一些我自认为需要多加练习的题目，它们并非是很难的，极不易理解的题目，而是对于我来说题目简单但是却不好写代码的、代码需要注意的细节多的和非常规思路的。这些题并不都是很难，但有些需要技巧

---

209.长度最小的子数组

209. 长度最小的子数组 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-size-subarray-sum/?envType=list&envId=ZCa7r67M这道题并不是所谓真正意义上的难题，而是我为了警示自己，要认真读题，这道题一开始做的时候我把大于等于target这一重要的解题关键信息，粗略的看成了等于target，做完了之后自然是没有ac，去看了官方题解，发现很不可思议，甚至觉得是测试用例出错了，相信大家也遇到过和我类似的情况吧，认真读题是关键

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left=0;int mincount=INT_MAX;int sum=0;
        for(int i=0;i<nums.size();++i){
            sum+=nums[i];
            while(sum>=target){
                mincount=min(mincount,i-left+1);//先做统计
                sum-=nums[left];++left;
            }
        }
        return mincount==INT_MAX?0:mincount;    
    }
};

为数不多我觉得需要注意的细节是：使用while循环缩小窗口而非if语句，这是因为如果遇上了前几个数很小，当前数字很大的情况，这时需要很快的情况窗口找答案，如果你用if去判断，看上去没什么问题，但是如果数组长度很小，你很容易找不到正确的答案，i就已经走到数组末尾了，也就是右窗口遍历的太快了，以至于虽然后面可能含有答案，你也拿不到了

还有一个注意的点是计数器mincount先做统计，再进行缩小窗口，不然也可以做出来，就是比较时候麻烦些而已。顺便说一下，也可以不让右窗口一直移到，这样就不用考虑这些，每次先判断窗口和与target比较，不过这样代码显得不够整洁

---

454.四数相加II

454. 四数相加 II - 力扣（LeetCode）https://leetcode.cn/problems/4sum-ii/?envType=list&envId=ZCa7r67M这道题是有技巧的，不过也相对其他题简单一些，解题思路是两个数组为一组，进行相加，把和录到哈希表map里，这里的键记录的是两个数相加的和，值记录的是这个和出现的次数，前两个数组和入到哈希表以后，再用0-另两个数组和看看能不能在map里找到。如果能则使res+=map【0-sum】
为什么是+=
之前我的想法是，每找到一次map对应的位置值--
但是是不对的，因为我们并不是重复计算了那个数字的个数，而是两数组的各个位置和都算了一遍，如果自减了，就很可能导致遍历第三四数组查找那个位置时，本次查找减没了，而下一次查找时候要用时候没有了
这里的道理和前两个数组相加求值需要累加道理是一样的，不同的位置加出来的和，肯定是下标不会重复的
去自行模拟一下【-1，-1】、【-1，1】、【-1，1】、【1，-1】
便可以知道

---

15.三数之和

15. 三数之和 - 力扣（LeetCode）https://leetcode.cn/problems/3sum/?envType=list&envId=ZCa7r67M看起来和上一道题是一样的题，一样的思路，其实不然，这道题其实不适合纯哈希表解决（反正我只用哈希表现在是超时的）

并且仔细看题目可以知道，上一道题是在四个数组里找和是target的，这道题是在一个数组里找三个数，它们的和等于0，看着差不多，但是不同的是三数之和需要对三元组进行去重，去重的需要使得使用哈希表变得十分困难。我们要在加法循环里使用set哈希辅助完成数据的存储，然后判断第二个数字去重，则更为麻烦

思路简单的来说是外层循环遍历第一个数，里层用set来避免元素重复使用，这次使用5这个数字和上次也使用5这个数字得到的结果是重复的，那如何判断呢就是要排序，并不仅仅是j>i&&nums【j-1】==nums【j】这样就去重了，比如说【0，0，0，0】这个数据，我们i第一次遍历到第一个数，里层循环遍历第二个数字，而我们此时在哈希表里找有没有第三个数字相加得到0，显然是找不到的，因为我们还没有开始放数在哈希表，然后进行j++，走到第三个0这个时候直接判断那步排重直接就跳出循环了，这是错误的。

并且放哈希表的数不是0-当前两个数字的和，而是放入当前第二个数遍历的数字，这也是当时很让我费解的，为什么不放入0-前两个数字的和也不放入第三个数而是选择放入第二个呢？这是因为0-前两个数和在整个数组不一定能找得到，这不是存在的数不能放进去，而第三个数字要想取得，是要再写循环的，这就失去了写哈希表的意义，也增大了时间复杂度

总的来说，在面试时用哈希很难写出题解，要注意很多细节，和剪枝，稍不留神就超时了，细节尤其是第二个数字的重复判断，我觉得不知道这个特殊测试用例的话，是很难想到bug出在哪里的！

ok说了这么多，我们来看看推荐的写法是什么？推荐的写法应该是排序和双指针的搭配解法，同样也需要排序，记住，大多数的需要去重的时候，都需要对数据排序。排序后，外层循环遍历第一个数，里层循环是双指针，一个指针☞i的下一个数字，另一个☞数组最后一个数字，因为已经排好序了，所以如果当前三个数加起来过大就使右指针向左移，反之左指针向右移。

这里排序起到了两个作用，一是使去重变得简单，二是使数据有规律后双指针能够调节，使答案更容易被找到

class Solution {
public:
    vector<vector<int>> threeSum(vector& nums) {
        sort(nums.begin(),nums.end());int sum=0;
        vector<vector<int>>res;int left=0,right=0;
        if(nums[0]>0)return res;
        for(int i=0;i<nums.size();++i){
            if(i>0&&nums[i]==nums[i-1])continue;
            int slow=i+1,fast=nums.size()-1;
            
            while(slow<fast){
            if(slow>i+1&&nums[slow]==nums[slow-1]){slow++;continue;}
            if(fast+1<nums.size()&&nums[fast]==nums[fast+1]){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. 四数之和 - 力扣（LeetCode）https://leetcode.cn/problems/4sum/?envType=list&envId=ZCa7r67M四数之和要比四数之和II是难一点的，不过思路也是类似三数之和的，可以说上一道题知道思路，这一道题也可以很容易的解出来。

也是排序去重+双指针解法，不同的是由于是四个数的和，所以外层是双for循环，然后里面还是双指针的思路，直接看代码

class Solution {
public:
    vector<vector<int>> fourSum(vector& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<vector<int>>res;
        for(int i=0;i<nums.size();++i){
            if(i>0&&nums[i]==nums[i-1])continue;
            for(int j=i+1;j<nums.size();++j){
                if(j>i+1&&nums[j]==nums[j-1])continue;
                int left=j+1,right=nums.size()-1;
                while(left<right){
                    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(left<right&&nums[left]==nums[left-1])left++;
                    while(left<right&&nums[right]==nums[right+1])right--;
                    }
                    else if((long)nums[i]+nums[j]+nums[left]+nums[right]>target)right--;
                    else left++;
                }
            }
        }
        return res;
    }
};

这个代码和上一道题的双指针循环里判断两个指针去重又有一些不同，但是思路是一样的，这道题的排重思路是如果此时找到了答案，那就直接进入先放到res数组里，然后去重，保证下一次找到的答案绝对不会重复，采用循环去重是正确的选择，因为可能连续几个答案都一样。

那为什么上一道题使用的是if呢？这能去重干净吗？

仔细看，它的去重是一进来就排重，而且排重完毕后continue，再判断一次，直到相邻不再重复，这其实和while是一样的效果，只是两种表达方式。

这道题是不能和四数之和II去类比的，应该和上一道题三数之和去比较，都不适合用哈希，同样的官方题解也并未给出哈希解法

---

以上便是这一期的全部内容，下一期同样也是不容易解的专题

都看到这里了如果有用的话别忘了一键三连哦，如果是互粉回访我也会做的！

大家有什么想看的题解，或者想看的算法专栏、数据结构专栏，可以去看看往期的文章，有想看的新题目或者专栏也可以评论区写出来，讨论一番，本账号将持续更新。
期待您的关注