目录
1.题目一
给定一个长度为
n的整数数组height。有n条垂线，第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线，使得它们与
x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
说明：你不能倾斜容器。
2.思路分析
- 1.在初始时，左右指针分别指向数组的左右两端
- 2.容水量：两个指针指向的最小值*指针之间的距离
- 3.每次以双指针为左右边界计算出的容量中的最大值。
3.代码实现
public int getMaxArea(int[] array) {
int left = 0, right = array.length - 1;//定义双指针
int maxArea = 0;//初始化最大面积
while (left < right) {
int area = Math.min(array[left], array[right]) * (right - left);//面积的计算
maxArea = Math.max(area, maxArea);//将面积与最大面积对比，取最大值
if (array[left] < array[right]) {
left++;//左指针移动
} else {
right--;//右指针移动
}
}
return maxArea;
}4.题目二
给你一个整数数组
nums，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且j != k，同时还满足nums[i] + nums[j] + nums[k] == 0。请你返回所有和为
0且不重复的三元组。注意：答案中不可以包含重复的三元组。
5.思路分析
- 1.先排序，排序后固定一个数array[i]，在使用双指针判断三数之和
- 2.如果array[i]大于0，三个数之和必然无法等于零，并跳过array[i]==array[i-1]
- 3.如果sum==0，但nums[L] == nums[L+1]会导致结果重复，L++跳过
- 4.如果sum==0，但nums[R] == nums[R-1]会导致结果重复，R--跳过
6.代码实现
public List<List<Integer>> getThreeSum(int[] array) {
List<List<Integer>> arr = new ArrayList<>();//定义空集合存储
if (array == null || array.length < 3) {
return arr;
}
Arrays.sort(array);//从小到大排序
for (int i = 0; i < array.length; i++) {
if (array[i] > 0) {//固定值为0，sum不可能为0
break;
}
if (i > 0 && array[i] == array[i + 1]) {//剔除重复值
continue;
}
//定义指针
int L = i + 1;
int R = array.length - 1;
while (L < R) {
int sum = array[i] + array[L] + array[R];//三数之和
if (sum == 0) {
arr.add(Arrays.asList(array[i], array[L], array[R]));//将数组转化为集合，存储
while (L < R && array[L] == array[L + 1]) {//剔除重复
L++;
}
while (L < R && array[R] == array[R - 1]) {//剔除重复
R--;
}
L++;
R--;
} else if (sum < 0) {
L++;
} else if (sum > 0) {
R++;
}
}
}
return arr;
}
