LeetCode热题100——双指针

---

1、移动零

1.1 题目链接

点击跳转到题目位置
1.2 题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组举行利用。
提示:

• 1 <= nums.length <= 104
  
• -231 <= nums <= 231 - 1
  

1.3 解题代码

1. class Solution {
2.     public void moveZeroes(int[] nums) {
3.         int left = 0;
4.         int right = 0;
5.         int n = nums.length;
6.         while(right < n){
7.             if(nums[right] != 0){
8.                 swap(nums, left, right);
9.                 left++;
10.             }
11.             right++;
12.         }
13.     }
15.     public void swap(int nums[], int left, int right){
16.         int temp = nums[left];
17.         nums[left] = nums[right];
18.         nums[right] = temp;
19.     }
20. }

复制代码

1.4 解题思绪

• 
  

2、盛最多水的容器

2.1 题目链接

点击跳转到题目位置
2.2 题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**阐明：**你不能倾斜容器。
提示：

• n == height.length
  
• 2 <= n <= 105
  
• 0 <= height <= 104
  

2.3 解题代码

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

复制代码

2.4 解题思绪

• 利用双指针来办理题目。
  
• 每次都盘算一下当前盛水量，并更新最大盛水量。如果左端高度小于等于右端，则左指针右移；如果左端高度高于右端，则右指针左移。
  

3、三数之和

3.1 题目链接

点击跳转到题目位置
3.2 题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums, nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包罗重复的三元组。
提示：

• 3 <= nums.length <= 3000
  
• -105 <= nums <= 105
  

3.3 解题代码

1. class Solution {
2.     public List<List<Integer>> threeSum(int[] nums) {
3.         List<List<Integer>> ret = new ArrayList<List<Integer>>();
4.         Arrays.sort(nums);
5.         int n = nums.length;
6.         if(n < 3){
7.             return ret;
8.         }
9.         if(nums[0] + nums[1] + nums[2] > 0){
10.             return ret;
11.         }
12.         for(int i = 0; i < n - 1; ++i){
13.             if(i != 0 && nums[i] == nums[i - 1]){
14.                 continue;
15.             }
16.             int left = i + 1;
17.             int right = n - 1;
18.             while(left < right){
19.                 int num = nums[i] + nums[left] + nums[right];
20.                 if(num < 0){
21.                     left++;
22.                 } else if(num > 0){
23.                     right--;
24.                 } else{
25.                     List<Integer> list = new ArrayList<Integer>();
26.                     list.add(nums[i]);
27.                     list.add(nums[left]);
28.                     list.add(nums[right]);
29.                     ret.add(list);
30.                     left++;
31.                     right--;
32.                     while(left < right && nums[left] == nums[left - 1]){
33.                         ++left;
34.                     }
35.                     while(left < right && nums[right] == nums[right + 1]){
36.                         --right;
37.                     }
38.                 }
39.             }
40.         }
41.     return ret;
42.     }
43. }

复制代码

3.4 解题思绪

• 首先将数组按照非递减顺序排序，如果数组长度小于3或者前3个数都大于0了，直接输出空数组即可。
  
• 接着遍历数组，如果下标不为0，则需要做去重利用（即不能与前面一个数相称）。
  
• 然后用双指针将题目转化成两数之和的题目，需要举行去重利用。
  

4、

4.1 题目链接

点击跳转到题目位置
4.2 题目描述

给定 n 个非负整数表现每个宽度为 1 的柱子的高度图，盘算按此分列的柱子，下雨之后能接多少雨水。
提示：

• n == height.length
  
• 1 <= n <= 2 * 104
  
• 0 <= height <= 105
  

4.3 解题代码

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

复制代码

4.4 解题思绪

• 前缀和+后缀和题目
  
• 前缀和负责维护当前位置及之前位置的所有的柱子的最高值。
  
• 后缀和负责维护当前位置及之后位置的所有的柱子的最高值。
  
• 当前位置的蓄水为当前位置的前缀和与后缀和的最小者减去当前高度。
  
• 累加总和即末了的答案。
  

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