文章目录
- 双指针
- 1. 删除有序数组中的重复项（入门）
- 1.1 题目描述
- 1.2 解题思路
- 1.3 代码实现
- 2. 删除有序数组中的重复项 II（简单）
- 2.1 题目描述
- 2.2 解题思路
- 2.3 代码实现
- 3. 移动零（简单）
- 3.1 题目描述
- 3.2 代码实现
- 4. 两数之和（入门）
- 4.1 题目描述
- 4.2 解题思路
- 4.3 代码实现
- 5. 盛水最多的容器（中等）
- 5.1 题目描述
- 5.2 解题思路
- 5.3 代码实现
- 6. 三数之和（中等）
- 6.1 题目描述
- 6.2 解题思路
- 6.3 代码实现
- 7. 最接近的三数之和（中等）
- 7.1 题目描述
- 7.2 解题思路
- 7.3 代码实现
- 8. 接雨水（中等）
- 8.1 题目描述
- 8.2 解题思路
- 8.3 代码实现
双指针
双指针一般是指利用两个变量，通过在线性的结构上进行遍历来解决某些特定的问题，按照遍历的方式一般多采用：同向遍历，相向遍历两种方式，例如冒泡排序、选择排序、插入排序都是用了两个变量同向遍历来实现，快排则是通过相向遍历来实现。
1. 删除有序数组中的重复项（入门）
1.1 题目描述
1.2 解题思路
快慢指针的简单应用
1.3 代码实现
public int removeDuplicates(int[] nums) {
int n = nums.length;
int p1 = 0;
int p2 = 1;
while (p2 < n) {
if (nums[p1] != nums[p2]) {
nums[++p1] = nums[p2];
}
p2++;
}
return p1 + 1;
}
leetcode跳转：26. 删除有序数组中的重复项
2. 删除有序数组中的重复项 II（简单）
2.1 题目描述
2.2 解题思路
与前一题结合在一起看，就是保留前X个相同数字，超过X个后，再进行比较，所以快指针逻辑不变，只需要让慢指针在比较时每次往前取两位即可。
2.3 代码实现
public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n <= 2) {
return n;
}
int p1 = 2;
int p2 = 2;
while (p2 < n) {
if (nums[p1 - 2] != nums[p2]) {
nums[p1] = nums[p2];
p1++;
}
p2++;
}
return p1;
}
leetcode跳转：80. 删除有序数组中的重复项II
3. 移动零（简单）
3.1 题目描述
3.2 代码实现
public void moveZeroes(int[] nums) {
int zero = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
int t = nums[i];
nums[i] = 0;
nums[zero] = t;
zero++;
}
}
}
leetcode跳转：283. 移动零
4. 两数之和（入门）
4.1 题目描述
4.2 解题思路
左右指针，相向遍历
4.3 代码实现
public int[] twoSum(int[] numbers, int target) {
int n = numbers.length;
int left = 0;
int right = n - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
} else if (sum > target) {
right--;
} else {
left++;
}
}
return null;
}
leetCode跳转：167. 两数之和 II - 输入有序数组
5. 盛水最多的容器（中等）
5.1 题目描述
5.2 解题思路
同样是一道左右指针，相向遍历的题，每次移动较短的柱子，盛水最多的容器，即为：间距 * min(left, right)
5.3 代码实现
public int maxArea(int[] height) {
int n = height.length;
int left = 0;
int right = n - 1;
int ans = 0;
while (left < right) {
int min = Math.min(height[left], height[right]);
ans = Math.max(ans, min * (right - left));
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return ans;
}
leetCode跳转：11. 盛水最多的容器
6. 三数之和（中等）
6.1 题目描述
6.2 解题思路
排序+双指针也是常见的组合解法，本题只需要排序后，再进行枚举即可。
两处优化
6.3 代码实现
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
if (nums[i] + nums[n - 1] + nums[n - 2] < 0) {
continue;
}
if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
break;
}
int k = n - 1;
for (int j = i + 1; j < k; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
while (j < k && nums[i] + nums[j] + nums[k] > 0) {
k--;
}
if (j == k) {
break;
}
if (nums[i] + nums[j] + nums[k] == 0) {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
ans.add(list);
}
}
}
return ans;
}
leetCode跳转：15. 三数之和
7. 最接近的三数之和（中等）
7.1 题目描述
7.2 解题思路
解法同三数之和
7.3 代码实现
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int ans = Integer.MAX_VALUE;
int n = nums.length;
for (int i = 0; i < n - 2; i++) {
int j = i + 1;
int k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
if (sum == target) {
return sum;
}
// 接近三数之和
if (Math.abs(sum - target) < Math.abs(ans - target)) {
ans = sum;
}
if (sum > target) {
k--;
} else {
j++;
}
}
}
return ans;
}
leetCode跳转：16. 最接近的三数之和
8. 接雨水（中等）
8.1 题目描述
8.2 解题思路
左右指针，相向遍历。
要求可接的雨水处的水量，可以先分别求出位于此处两侧最长柱子的高度，然后取其较短的一根即表示其可接水量的上限，因此完全可以通过不断的左右遍历（收缩较短的柱子）的方式计算出每个位置可接的水量。
8.3 代码实现
public int trap(int[] height) {
int n = height.length;
int leftMax = 0;
int rightMax = 0;
int left = 0;
int right = n - 1;
int ans = 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;
}
leetCode跳转：42. 接雨水
