LeetCode热题100——双指针

文章目录

• 1、移动零
• • 1.1 题目链接
  • 1.2 题目描述
  • 1.3 解题代码
  • 1.4 解题思路
• 2、盛最多水的容器
• • 2.1 题目链接
  • 2.2 题目描述
  • 2.3 解题代码
  • 2.4 解题思路
• 3、三数之和
• • 3.1 题目链接
  • 3.2 题目描述
  • 3.3 解题代码
  • 3.4 解题思路
• 4、
• • 4.1 题目链接
  • 4.2 题目描述
  • 4.3 解题代码
  • 4.4 解题思路

1、移动零

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

提示:

• 1 <= nums.length <= 10⁴
• -2³¹ <= nums[i] <= 2³¹ - 1

1.3 解题代码

class Solution { public void moveZeroes(int[] nums) { int left = 0; int right = 0; int n = nums.length; while(right < n){ if(nums[right] != 0){ swap(nums, left, right); left++; } right++; } } public void swap(int nums[], int left, int right){ int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; }}

1.4 解题思路

2、盛最多水的容器

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

**说明：**你不能倾斜容器。

提示：

• n == height.length
• 2 <= n <= 10⁵
• 0 <= height[i] <= 10⁴

2.3 解题代码

class Solution { public int maxArea(int[] height) { int left = 0; int right = height.length - 1; int ret = 0; while(left < right){ ret = Math.max(ret, Math.min(height[left], height[right]) * (right - left)); if(height[left] <= height[right]){ ++left; } else{ right--; } } return ret; }}

2.4 解题思路

1. 使用双指针来解决问题。
2. 每次都计算一下当前盛水量，并更新最大盛水量。如果左端高度小于等于右端，则左指针右移；如果左端高度高于右端，则右指针左移。

3、三数之和

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

提示：

• 3 <= nums.length <= 3000
• -10⁵ <= nums[i] <= 10⁵

3.3 解题代码

class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ret = new ArrayList<List<Integer>>(); Arrays.sort(nums); int n = nums.length; if(n < 3){ return ret; } if(nums[0] + nums[1] + nums[2] > 0){ return ret; } for(int i = 0; i < n - 1; ++i){ if(i != 0 && nums[i] == nums[i - 1]){ continue; } int left = i + 1; int right = n - 1; while(left < right){ int num = nums[i] + nums[left] + nums[right]; if(num < 0){  left++; } else if(num > 0){  right--; } else{  List<Integer> list = new ArrayList<Integer>();  list.add(nums[i]);  list.add(nums[left]);  list.add(nums[right]);  ret.add(list);  left++;  right--;  while(left < right && nums[left] == nums[left - 1]){ ++left;  }  while(left < right && nums[right] == nums[right + 1]){ --right;  } } } } return ret; }}

3.4 解题思路

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

4、

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

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

提示：

• n == height.length
• 1 <= n <= 2 * 10⁴
• 0 <= height[i] <= 10⁵

4.3 解题代码

class Solution { public int trap(int[] height) { int n = height.length; int[] prefix_sum = new int[n]; int[] suffix_sum = new int[n]; for(int i = 0; i < n; ++i){ if(i == 0){ prefix_sum[i] = height[i]; } else{ prefix_sum[i] = Math.max(prefix_sum[i - 1], height[i]); } } for(int i = n - 1; i >= 0; --i){ if(i == n - 1){ suffix_sum[i] = height[i]; } else{ suffix_sum[i] = Math.max(suffix_sum[i + 1], height[i]); } } int ret = 0; for(int i = 0; i < n; ++i){ ret += (Math.min(prefix_sum[i], suffix_sum[i]) - height[i]); } return ret; }}

4.4 解题思路

1. 前缀和+后缀和问题
2. 前缀和负责维护当前位置及之前位置的所有的柱子的最高值。
3. 后缀和负责维护当前位置及之后位置的所有的柱子的最高值。
4. 当前位置的蓄水为当前位置的前缀和与后缀和的最小者减去当前高度。
5. 累加总和即最后的答案。