《LeetCode热题100》---＜双指针篇四道②＞
本篇博客讲解LeetCode热题100道双指针篇中的第三道：三数之和（中等）
第四道：接雨水（困难）
第三道：三数之和（中等）
https://i-blog.csdnimg.cn/direct/23c126a6ee6a4a53b9c09922aaff1d0b.png
法一：暴力枚举（三重循环）
三重循环，分别枚举三个数，找出符合条件的数并用集合返回。
法二：排序+双指针
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 > 0) {
break;
}
int l = i + 1, r = n - 1;
int target = -nums;
while (l < r) {
int sum = nums + nums;
if (sum < target) {
l++;
} else if (sum > target) {
r--;
} else {
ret.add(new ArrayList<Integer>(Arrays.asList(nums, nums, nums)));
l++;
r--;
while (l < r && nums == nums) {
l++;
}
while (l < r && nums == nums) {
r--;
}
}
}
i++;
while (i< n- 2 && nums == nums) {
i++;
}
}
return ret;
}
} 上次我们利用哈希表求解了两数之和。
这次我们利用排序+双指针求解三数之和。
首先标题形貌：找到其中三个数，它们的和为。假如有多组一起返回。不能重复，返回相同的数字，因此还要去重。假如没有返回空。
1.我们利用排序来去掉重复解。
2.利用双指针探求所有解。
①我们确定好第一个元素为num，探求剩下两个数字＝0-num。也就是-num。这样我们相称于把求解三数之和的题目转化为求解两数之和。
②利用双指针求解剩下两数之和。
假如两数之和大于目标值，则让right--
假如两数之和小于目标值，则让left++
假如等于，那么将这三个数添加到list集合当中。
重点：去重
在left < right的情况下，假如num =num 则不断让left++。直到不相等
right去重的同理。
第四道：接雨水（困难）
https://i-blog.csdnimg.cn/direct/b36e59fe4ef94e15bf27a3e4ed791fe5.png
法一：动态规划
class Solution {
public int trap(int[] height) {
int n = height.length;
if (n == 0) {
return 0;
}
int[] leftMax = new int;
leftMax = height;
for (int i = 1; i < n; ++i) {
leftMax = Math.max(leftMax, height);
}
int[] rightMax = new int;
rightMax = height;
for (int i = n - 2; i >= 0; --i) {
rightMax = Math.max(rightMax, height);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += Math.min(leftMax, rightMax) - height;
}
return ans;
}
} 1.正向遍历数组 height 得到数组 leftMax 的每个元素值，
2.反向遍历数组 height 得到数组 rightMax 的每个元素值
3.在得到数组 leftMax 和 rightMax 的每个元素值之后，对于 0≤i<n，下标 i 处能接的雨水量等于 min(leftMax,rightMax)−height。遍历每个下标位置即可得到能接的雨水总量。
法二：单调栈
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 > height) {
int top = stack.pop();
if (stack.isEmpty()) {
break;
}
int left = stack.peek();
int currWidth = i - left - 1;
int currHeight = Math.min(height, height) - height;
ans += currWidth * currHeight;
}
stack.push(i);
}
return ans;
}
} 1.从左到右遍历数组，遍历到下标 i 时，假如栈内至少有两个元素，记栈顶元素为 top，top 的下面一个元素是 left，则一定有 height≥height。
2.假如 height>height，则得到一个可以接雨水的地区，该地区的宽度是 i−left−1，高度是 min(height,height)−height，根据宽度和高度即可计算得到该地区能接的雨水量。
3.为了得到 left，必要将 top 出栈。在对 top 计算能接的雨水量之后，left 酿成新的 top，重复上述操纵，直到栈变为空，大概栈顶下标对应的 height 中的元素大于或等于 height。
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);
rightMax = Math.max(rightMax, height);
if (height < height) {
ans += leftMax - height;
++left;
} else {
ans += rightMax - height;
--right;
}
}
return ans;
}
} 1.初始化leftMax和rightMax=0.用于记录每次的最左边最大值和最右边最大值
2.在l<r的情况下循环，找到每一次的最左边最大值，和最右边最大值。
3.假如左边的比右边小（低），那么加上雨水的值为leftMax减去此时left的高度。并left++
4.假如右边的比左边小（低），那么加上雨水的值为rightMax减去此时right的高度。并right--
5.循环完毕之后通过累加我们就得到了终极答案。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]