当前位置：首页 > news >正文

每日两道力扣，day6

news 2026/6/5 20:22:12

每日两道力扣，day6

每日两道力扣，今天是：

11. 盛最多水的容器 - 力扣（LeetCode）

15. 三数之和 - 力扣（LeetCode）

第一题：盛最多水的容器

11. 盛最多水的容器 - 力扣（LeetCode）

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.细节：

这个题需要理解木桶效应，以及示例图。较为简单，类似小学课本上的看图说话。

第二题：三数之和

15.三数之和-力扣leetcode

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; } };