《LeetCode热题100》---＜双指针篇四道②＞

本篇博客讲解LeetCode热题100道双指针篇中的
  第三道：三数之和（中等）
  第四道：接雨水（困难）
  第三道：三数之和（中等）

法一：暴力枚举（三重循环）

   三重循环，分别枚举三个数，找出符合条件的数并用集合返回。
  法二：排序+双指针 

1. class Solution {
2.     public List<List<Integer>> threeSum(int[] nums) {
3.         List<List<Integer>> ret = new ArrayList<>();
4.         //1.排序
5.         Arrays.sort(nums);
6.         int n = nums.length;
7.         //2.利用双指针解决问题
8.         for (int i = 0; i < n - 2; ) {
9.             if (nums[i] > 0) {
10.                 break;
11.             }
12.             int l = i + 1, r = n - 1;
13.             int target = -nums[i];
15.             while (l < r) {
16.                 int sum = nums[l] + nums[r];
17.                 if (sum < target) {
18.                     l++;
19.                 } else if (sum > target) {
20.                     r--;
21.                 } else {
22.                     ret.add(new ArrayList<Integer>(Arrays.asList(nums[l], nums[r], nums[i])));
23.                     l++;
24.                     r--;
25.                     while (l < r && nums[l - 1] == nums[l]) {
26.                         l++;
27.                     }
28.                     while (l < r && nums[r + 1] == nums[r]) {
29.                         r--;
30.                     }
31.                 }
32.             }
33.             i++;
34.             while (i< n- 2 && nums[i] == nums[i - 1]) {
35.                 i++;
36.             }
37.         }
38.         return ret;
39.     }
40. }

复制代码

  上次我们利用哈希表求解了两数之和。
  这次我们利用排序+双指针求解三数之和。
  首先标题形貌：找到其中三个数，它们的和为。假如有多组一起返回。不能重复，返回相同的数字，因此还要去重。假如没有返回空。
  1.我们利用排序来去掉重复解。
  2.利用双指针探求所有解。
  ①我们确定好第一个元素为num，探求剩下两个数字＝0-num。也就是-num。这样我们相称于把求解三数之和的题目转化为求解两数之和。
  ②利用双指针求解剩下两数之和。
  假如两数之和大于目标值，则让right--
  假如两数之和小于目标值，则让left++
  假如等于，那么将这三个数添加到list集合当中。
  重点：去重
  在left <  right的情况下，假如num[left] =num [left+1] 则不断让left++。直到不相等
  right去重的同理。
  

---

第四道：接雨水（困难）

 法一：动态规划

1. class Solution {
2.     public int trap(int[] height) {
3.         int n = height.length;
4.         if (n == 0) {
5.             return 0;
6.         }
8.         int[] leftMax = new int[n];
9.         leftMax[0] = height[0];
10.         for (int i = 1; i < n; ++i) {
11.             leftMax[i] = Math.max(leftMax[i - 1], height[i]);
12.         }
14.         int[] rightMax = new int[n];
15.         rightMax[n - 1] = height[n - 1];
16.         for (int i = n - 2; i >= 0; --i) {
17.             rightMax[i] = Math.max(rightMax[i + 1], height[i]);
18.         }
20.         int ans = 0;
21.         for (int i = 0; i < n; ++i) {
22.             ans += Math.min(leftMax[i], rightMax[i]) - height[i];
23.         }
24.         return ans;
25.     }
26. }

复制代码

  1.正向遍历数组 height 得到数组 leftMax 的每个元素值，
  2.反向遍历数组 height 得到数组 rightMax 的每个元素值
  3.在得到数组 leftMax 和 rightMax 的每个元素值之后，对于 0≤i<n，下标 i 处能接的雨水量等于 min(leftMax,rightMax)−height。遍历每个下标位置即可得到能接的雨水总量。 
  法二：单调栈

1. class Solution {
2.     public int trap(int[] height) {
3.         int ans = 0;
4.         Deque<Integer> stack = new LinkedList<Integer>();
5.         int n = height.length;
6.         for (int i = 0; i < n; ++i) {
7.             while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
8.                 int top = stack.pop();
9.                 if (stack.isEmpty()) {
10.                     break;
11.                 }
12.                 int left = stack.peek();
13.                 int currWidth = i - left - 1;
14.                 int currHeight = Math.min(height[left], height[i]) - height[top];
15.                 ans += currWidth * currHeight;
16.             }
17.             stack.push(i);
18.         }
19.         return ans;
20.     }
21. }

复制代码

  1.从左到右遍历数组，遍历到下标 i 时，假如栈内至少有两个元素，记栈顶元素为 top，top 的下面一个元素是 left，则一定有 height[left]≥height[top]。
  2.假如 height>height[top]，则得到一个可以接雨水的地区，该地区的宽度是 i−left−1，高度是 min(height[left],height)−height[top]，根据宽度和高度即可计算得到该地区能接的雨水量。
  3.为了得到 left，必要将 top 出栈。在对 top 计算能接的雨水量之后，left 酿成新的 top，重复上述操纵，直到栈变为空，大概栈顶下标对应的 height 中的元素大于或等于 height。
  4.在对下标 i 处计算能接的雨水量之后，将 i 入栈，继续遍历后面的下标，计算能接的雨水量。遍历竣事之后即可得到能接的雨水总量。
   法三：双指针

1. class Solution {
2.     public int trap(int[] height) {
3.         int ans = 0;
4.         int left = 0, right = height.length - 1;
5.         int leftMax = 0, rightMax = 0;
6.         while (left < right) {
7.             leftMax = Math.max(leftMax, height[left]);
8.             rightMax = Math.max(rightMax, height[right]);
9.             if (height[left] < height[right]) {
10.                 ans += leftMax - height[left];
11.                 ++left;
12.             } else {
13.                 ans += rightMax - height[right];
14.                 --right;
15.             }
16.         }
17.         return ans;
18.     }
19. }

复制代码

  1.初始化leftMax和rightMax=0.用于记录每次的最左边最大值和最右边最大值
  2.在l<r的情况下循环，找到每一次的最左边最大值，和最右边最大值。
  3.假如左边的比右边小（低），那么加上雨水的值为leftMax减去此时left的高度。并left++
  4.假如右边的比左边小（低），那么加上雨水的值为rightMax减去此时right的高度。并right--
  5.循环完毕之后通过累加我们就得到了终极答案。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。