每日两道力扣，day6

每日两道力扣day6每日两道力扣day6每日两道力扣今天是11. 盛最多水的容器 - 力扣LeetCode15. 三数之和 - 力扣LeetCode第一题盛最多水的容器11. 盛最多水的容器 - 力扣LeetCode1.思路在写这个题之前咱们需要了解一个经典原理——木桶效应。显然在相同底面积的情况下木桶盛水的最大值由最短的那块板决定。这个题很明显是双指针算法的应用场景。因为这个题目给出的是一个平面切割图咱们定义left,right左右两个指针。底面积S right - left。高度应是min(height[left],height[right])所以体积v就是这二者的乘积。观察题目给的示例图当height[left] height[right] 时left应该往右移动。反之right应该往左移动。因为数组有限我们只需要保证程序不会运行超时即可剩下的交给计算机的算力。2.代码实现class Solution { public: int maxArea(vectorint height) { int left 0, right height.size() - 1; int ret 0; while(left right) { int v min(height[left], height[right]) * (right - left); ret max(v,ret); if(height[left] height[right]) left; else right--; } return ret; } };3.细节这个题需要理解木桶效应以及示例图。较为简单类似小学课本上的看图说话。第二题三数之和15.三数之和-力扣leetcode1.思路在写这道题的时候我不知道大家有没有写过两数之和。有句话是这么说的有人相爱有人夜里看海有人leetcode第一题要用两个for循环。小编就属于for循环大军里的一员不过那个题我其实还会两种解法排序双指针哈希这个是看题解才知道的我那会还没学到哈希呢。同样的这道三数之和咱们也可以运用三个for循环暴力求解但是我感觉99.99%会超时。3个for循环时间复杂度是O(N3)你小子要是在面试的时候敢这样写面试官分分钟让你进人才管理库。还记得咱们昨天讲的双指针算法具有降维的特点吗暴力法要用3个for循环时间复杂度是O(N3)我们直接降为O(N2)。优雅太优雅了。具体落实的话是第一步利用sort将数组排序第二步双指针算法里面定义一个target -nums[i]第三步将nums[left] 与nums[rifght]的和同target比较大小推进左右指针然后得到一组解但是我按照这三步落实代码的时候测试样例跑不满说明我们的代码还是存在可以优化的地方。这个时候我们就得想一想哪里是不够完美的不够优雅的呢1是sort吗当然不是啊我们只是调了一个库函数sort帮我们将数组排序。2那既然排好序了所以大小关系肯定是nums[i] nums[left] nums[right]咯而我们在双指针算法里面定义一个target -nums[i]那当nums[i] 0的时候那必然是不存在解的所以我们直接break就好了。3在经历2的优化后我们发现测试样例还是跑不满。会出现重复的多余答案。显然对于nums[i]而言当i后nums[i]很可能和nusm[i-1]相等啊。这个逻辑bug刚好和咱们的实践吻合因此咱们必须把这里给优化。在i后写一个while循环当i n nums[i] nums[i-1]在防止数组越界的前提下让i往后走一步。2.代码实现class Solution { public: vectorvectorint threeSum(vectorint nums) { vectorvectorint ret; sort(nums.begin(),nums.end()); int n nums.size(); for(int i 0; i n; ) { int target -nums[i]; int left i1; int right n - 1; while(left right) { //因为已经排完序了 //优化1 if(nums[i] 0) break; if(nums[left] nums[right] target) { right--; } else if(nums[left] nums[right] target) { left; } else { ret.push_back({nums[i],nums[left],nums[right]}); left; right--; //跑不满啊不要忘记我们是已经排好序了的 //所以我又来优化了 //优化2. while(left right nums[left] nums[left-1]) left; while(left right nums[right] nums[right1]) right--; } } //还是跑不满不要忘记我们是已经排好序了的 //优化3. i; while(i n nums[i] nums[i-1]) i; } return ret; } };3.细节这个题的话不需要用到long long但必须看懂思路里面的优化部分不然就只能进人才管理库了。先打个预防针咱们明天要更新的是四数之和接雨水。估计会很难各位请做好心理准备。好了今天的每日两道力扣到这里就算是结束了看完是不是感觉有所收获呢如果学有所获的话麻烦给个三连支持一下呗。感谢观看您的支持将是我前进路上的重要动力。