《LeetCode热题100》---＜双指针篇四道②＞
本篇博客讲解LeetCode热题100道双指针篇中的 第三道：三数之和（中等） 第四道：接雨水（困难）
法一：暴力枚举（三重循环）
三重循环，分别枚举三个数，找出符合条件的数并用集合返回。
法二：排序+双指针
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ret = new ArrayList<>();
//1.排序
Arrays.sort(nums);
int n = nums.length;
//2.利用双指针解决问题
for (int i = 0; i < n - 2; ) {
if (nums[i] > 0) {
break;
}
int l = i + 1, r = n - 1;
int target = -nums[i];
while (l < r) {
int sum = nums[l] + nums[r];
if (sum < target) {
l++;
} else if (sum > target) {
r--;
} else {
ret.add(new ArrayList<Integer>(Arrays.asList(nums[l], nums[r], nums[i])));
l++;
r--;
while (l < r && nums[l - 1] == nums[l]) {
l++;
}
while (l < r && nums[r + 1] == nums[r]) {
r--;
}
}
}
i++;
while (i< n- 2 && nums[i] == nums[i - 1]) {
i++;
}
}
return ret;
}
}上次我们使用哈希表求解了两数之和。 这次我们使用排序+双指针求解三数之和。 首先题目描述：找到其中三个数，它们的和为。如果有多组一起返回。不能重复，返回相同的数字，因此还要去重。如果没有返回空。 1.我们利用排序来去掉重复解。 2.利用双指针寻找所有解。 ①我们确定好第一个元素为num[i]，寻找剩下两个数字＝0-num[i]。也就是-num[i]。这样我们相当于把求解三数之和的问题转化为求解两数之和。 ②利用双指针求解剩下两数之和。 如果两数之和大于目标值，则让right-- 如果两数之和小于目标值，则让left++ 如果等于，那么将这三个数添加到list集合当中。 重点：去重 在left < right的情况下，如果num[left] =num [left+1] 则不断让left++。直到不相等 right去重的同理。
第四道：接雨水（困难）
法一：动态规划
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return ans;
}
}1.正向遍历数组 height 得到数组 leftMax 的每个元素值， 2.反向遍历数组 height 得到数组 rightMax 的每个元素值 3.在得到数组 leftMax 和 rightMax 的每个元素值之后，对于 0≤i<n，下标 i 处能接的雨水量等于 min(leftMax[i],rightMax[i])−height[i]。遍历每个下标位置即可得到能接的雨水总量。
法二：单调栈
class Solution {
public int trap(int[] height) {
int ans = 0;
Deque<Integer> stack = new LinkedList<Integer>();
int n = height.length;
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int top = stack.pop();
if (stack.isEmpty()) {
break;
}
int left = stack.peek();
int currWidth = i - left - 1;
int currHeight = Math.min(height[left], height[i]) - height[top];
ans += currWidth * currHeight;
}
stack.push(i);
}
return ans;
}
}1.从左到右遍历数组，遍历到下标 i 时，如果栈内至少有两个元素，记栈顶元素为 top，top 的下面一个元素是 left，则一定有 height[left]≥height[top]。 2.如果 height[i]>height[top]，则得到一个可以接雨水的区域，该区域的宽度是 i−left−1，高度是 min(height[left],height[i])−height[top]，根据宽度和高度即可计算得到该区域能接的雨水量。 3.为了得到 left，需要将 top 出栈。在对 top 计算能接的雨水量之后，left 变成新的 top，重复上述操作，直到栈变为空，或者栈顶下标对应的 height 中的元素大于或等于 height[i]。 4.在对下标 i 处计算能接的雨水量之后，将 i 入栈，继续遍历后面的下标，计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。
法三：双指针
class Solution {
public int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
++left;
} else {
ans += rightMax - height[right];
--right;
}
}
return ans;
}
}1.初始化leftMax和rightMax=0.用于记录每次的最左边最大值和最右边最大值 2.在l<r的情况下循环，找到每一次的最左边最大值，和最右边最大值。 3.如果左边的比右边小（低），那么加上雨水的值为leftMax减去此时left的高度。并left++ 4.如果右边的比左边小（低），那么加上雨水的值为rightMax减去此时right的高度。并right-- 5.循环完毕之后通过累加我们就得到了最终答案。
腾讯云开发者
