11. 盛水最多的容器
题目描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明： 你不能倾斜容器。
示例1:
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1]
输出：1
提示：
n == height.length2 <= n <= 10^50 <= height[i] <= 10^4
分析
暴力
这个最简单的做法是使用两个for循环，固定1块板子，然后求这块板子到其他板子的盛水容量，如下
int max = 0;
for(int i = 0; i < height.length - 1; i++){
for(int j = i + 1; j < height.length; j++){
max = Math.max(max, Math.min(height[i], height[j]) * (j - i));
}
}
return max;
不过这个做法有问题。力扣直接判定其超出时间限制了
毕竟他的时间复杂度达到了 O(n^2) 。这就算不上是一个好的算法了。所以我们需要考虑一个更加好的算法。
双指针
双指针 也是这道题的考点。我们假设在初始时，指针分别指向左右两端，接下来要做的就是将指针向内移动，为了获得可能的最大值，这就是这道题我们需要好好考虑的地方了。我们知道容水量的计算公式如下:
容水量 = 两个指针指向的数字中较小值 * 指针之间的距离
既然我们要将指针向内移动，那么 指针之间的距离 一定是在减小的，为了让 容水量 更大，那么我们就希望 两个指针指向的数字中较小值 就要尽可能的大。所以对于指针向内移动的规则就是选取两个指针中高度矮的那个向内移动，这样就有“可能”找到比当前更大的容水量。
当左侧指针的位置碰上右侧指针或者在右侧指针右侧时即为遍历结束了。
解答
class Solution {
public int maxArea(int[] height) {
int left = 0; // 左侧指针
int right = height.length - 1; // 右侧指针
int max = 0;
while(left < right){
// 计算当前指针所在位置下的容水量并与max比较
int currentArea = (right - left) * Math.min(height[left], height[right]);
max = Math.max(max, currentArea);
// 将高度低那一侧的指针向内移动一步
if(height[left] > height[right]){
right--;
}else{
left++;
}
}
return max;
}
}
复杂度分析
- 时间复杂度：
left从0开始，right从n - 1开始，每次循环至少移动一个指针。两个指针总共最多移动n - 1次，每次计算当前容水量都是 O(1)，所以总体是线性的。 - 空间复杂度：只使用了
left、right、max、currentArea等常数个变量，没有额外开辟与n相关的空间，所以复杂度为 O(1) 。
为什么移动较矮的那根，不会漏掉最优解？
假设当前左指针高度为 h[left]，右指针为 h[right]，且 h[left] < h[right]。
当前容水量 = h[left] * (right - left)。
此时如果我们移动较高的右指针，新的距离是 right - 1 - left，而新的高度取决于 min(h[left], h[right-1])，它的值永远不可能大于 h[left]（因为 h[left] 是短板）。
也就是说，如果我们移动较高的指针，容水量只会变小（或不变），绝对不可能变大。所以我们只能移动较矮的指针，去赌下一个高度可能会更高。
15. 三数之和
题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
分析
暴力
最直接的做法是用三层循环枚举所有三元组，判断 nums[i] + nums[j] + nums[k] == 0，再用 Set 去重。
但时间复杂度是 O(n^3)，当n过多时一定会超时的，所以需要更优的算法。
排序 + 双指针
这道题的经典解法是：先排序，再固定第一个数，把问题转化成两数之和，然后用双指针求解。
具体思路如下：
- 先对数组
nums排序。 - 遍历数组，固定第一个数
nums[i]。 - 因为要找
nums[i] + nums[j] + nums[k] == 0，所以等价于在nums[i + 1 ... n - 1]中找两个数，使它们的和等于-nums[i]。 - 由于数组已经有序，可以用左右双指针：
left = i + 1right = n - 1target = -nums[i]
- 当
left < right时：
- 如果
nums[left] + nums[right] == target，说明找到一组解，加入结果集。 - 如果和小于
target，说明需要更大的和，所以left++。 - 如果和大于
target，说明需要更小的和，所以right--。
- 去重：
- 外层遍历时，如果
nums[i] == nums[i - 1]，说明这个第一个数已经处理过，跳过。 - 找到一组解后，跳过重复的
nums[left]和nums[right]，避免结果集中出现重复三元组。
- 提前结束：
- 如果
nums[i] > 0，因为数组已经升序，后面不可能再凑出和为0的三元组，直接break。
解答
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// 先判空，再排序
if (nums == null || nums.length < 3) {
return result;
}
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
// 如果当前数字大于 0，则三数之和一定大于 0，结束循环
if (nums[i] > 0) {
break;
}
// 跳过重复的 nums[i]
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = n - 1;
int target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 跳过重复的 left
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
// 跳过重复的 right
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
}
复杂度分析：
- 时间复杂度：排序需要 O(n log n)，外层循环 O(n)，内层双指针 O(n)，所以总体是 O(n^2)。
- 空间复杂度：不考虑结果集时，主要是排序使用的栈空间， O(log n)。