每日两道力扣，day6
每日两道力扣，day6
每日两道力扣，day6
每日两道力扣，今天是：
第一题：盛最多水的容器
1.思路：
在写这个题之前，咱们需要了解一个经典原理——木桶效应。
显然，在相同底面积的情况下，木桶盛水的最大值，由最短的那块板决定。这个题很明显是双指针算法的应用场景。因为这个题目给出的是一个平面切割图，咱们定义left,right左右两个指针。底面积S = right - left。高度应是min(height[left],height[right])，所以体积v就是这二者的乘积。观察题目给的示例图，当height[left] < height[right] 时，left应该往右移动。反之，right应该往左移动。因为数组有限，我们只需要保证程序不会运行超时即可，剩下的交给计算机的算力。
2.代码实现：
class Solution { public: int maxArea(vector<int>& 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.细节：
这个题需要理解木桶效应，以及示例图。较为简单，类似小学课本上的看图说话。
第二题：三数之和
1.思路：
在写这道题的时候，我不知道大家有没有写过两数之和。有句话是这么说的：有人相爱，有人夜里看海，有人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: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; sort(nums.begin(),nums.end()); int n = nums.size(); for(int i = 0; i < n; ) { int target = -nums[i]; int left = i+1; 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[right+1]) right--; } } //还是跑不满，不要忘记我们是已经排好序了的 //优化3. i++; while(i < n && nums[i] == nums[i-1]) i++; } return ret; } }; 3.细节：
这个题的话不需要用到long long，但必须看懂思路里面的优化部分，不然就只能进人才管理库了。
先打个预防针，咱们明天要更新的是四数之和，接雨水。估计会很难，各位请做好心理准备。
好了，今天的每日两道力扣到这里就算是结束了，看完是不是感觉有所收获呢？如果学有所获的话，麻烦给个三连支持一下呗。感谢观看，您的支持，将是我前进路上的重要动力。
