力扣热题 100：双指针专题四道题详细解析(JAVA)

在力扣（LeetCode）平台上，热题 100 是许多开发者提升算法能力的必刷清单。今天，我们就来详细解析热题 100 中与双指针相关的四道题，帮助大家更好地理解解题思路和技巧。

一、移动零

1. 题目描述

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

注意：必须在原数组上操作，不能拷贝额外的数组。

2. 示例

示例 1：

输入：nums = [0, 1, 0, 3, 12]

输出：[1, 3, 12, 0, 0]

解释：将所有 0 移动到数组末尾，非零元素的相对顺序保持不变。

3. 解题思路

这道题主要考察双指针的应用。我们可以使用两个指针，一个指针 i 用于遍历数组，另一个指针 j 用于记录非零元素的位置。具体步骤如下：

1. 初始化两个指针 i 和 j，都指向数组的起始位置。
2. 遍历数组，如果 nums[i] 不为零，则将 nums[i] 移动到 nums[j]，并将 j 向后移动一位。
3. 遍历结束后，将 j 之后的元素全部设置为零。

4. 代码实现（Java）

public class Solution {
    public void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j] = nums[i];
                j++;
            }
        }
        for (int i = j; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是数组的长度。我们只需要遍历数组两次，每次遍历的时间复杂度都是 O(n)。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

二、盛最多水的容器

1. 题目描述

给定一个数组 height ，表示若干个容器的高度。每个容器的宽度为 1，两个容器之间的距离为它们的下标之差。求能盛最多水的容器的面积。

2. 示例

示例 1：

输入：height = [1, 8, 6, 2, 5, 4, 8, 3, 7]

输出：49

解释：最大的面积是由高度为 7 和 8 的容器组成的，面积为 7 * 7 = 49。

3. 解题思路

这道题主要考察双指针的应用。我们可以使用两个指针，一个指针 left 指向数组的起始位置，另一个指针 right 指向数组的末尾。具体步骤如下：

1. 初始化两个指针 left 和 right，分别指向数组的起始位置和末尾位置。
2. 计算当前两个指针之间的面积，更新最大面积。
3. 移动较短的指针向中间移动一位，重复步骤 2，直到两个指针相遇。

4. 代码实现（Java）

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

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次，每次移动一个指针。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

三、三数之和

1. 题目描述

给定一个数组 nums，找出所有和为零的三元组。

注意：不能包含重复的三元组。

2. 示例

示例 1：

输入：nums = [-1, 0, 1, 2, -1, -4]

输出：[[-1, -1, 2], [-1, 0, 1]]

解释：和为零的三元组有 [-1, -1, 2] 和 [-1, 0, 1]。

3. 解题思路

这道题主要考察双指针的应用和排序。我们可以先对数组进行排序，然后使用双指针来查找和为零的三元组。具体步骤如下：

1. 对数组进行排序。
2. 遍历数组，对于每个元素 nums[i]，使用双指针 left 和 right 分别指向 i + 1 和数组末尾。
3. 计算 nums[i] + nums[left] + nums[right] 的和，如果和为零，则记录该三元组，并移动指针跳过重复元素。
4. 如果和小于零，则移动 left 指针向右移动一位；如果和大于零，则移动 right 指针向左移动一位。
5. 重复步骤 3 和 4，直到 left 小于 right。

4. 代码实现（Java）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

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

5. 复杂度分析

• 时间复杂度 ：O(n^2)，其中 n 是数组的长度。我们先对数组进行排序，时间复杂度为 O(n log n)，然后使用双指针遍历数组，时间复杂度为 O(n^2)。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间（不包括结果列表）。

四、接雨水

1. 题目描述

给定一个数组 height，表示若干个柱子的高度。每个柱子的宽度为 1，两个柱子之间的距离为它们的下标之差。求每个柱子可以接住的雨水量。

2. 示例

示例 1：

输入：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

输出：6

解释：可以接住的雨水量为 6。

3. 解题思路

这道题主要考察双指针的应用和动态规划。我们可以使用两个指针，一个指针 left 指向数组的起始位置，另一个指针 right 指向数组的末尾。具体步骤如下：

1. 初始化两个指针 left 和 right，分别指向数组的起始位置和末尾位置。
2. 初始化两个变量 leftMax 和 rightMax，分别记录左边和右边的最大高度。
3. 遍历数组，计算每个柱子可以接住的雨水量。
4. 如果 height[left] 小于 height[right]，则移动 left 指针向右移动一位；否则，移动 right 指针向左移动一位。
5. 重复步骤 3 和 4，直到 left 小于 right。

4. 代码实现（Java）

public class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int water = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    water += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    water += rightMax - height[right];
                }
                right--;
            }
        }
        return water;
    }
}

5. 复杂度分析

• 时间复杂度 ：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次，每次移动一个指针。
• 空间复杂度 ：O(1)，我们只使用了常数级别的额外空间。

以上就是力扣热题 100 中与双指针相关的四道题的详细解析，希望对大家有所帮助。在实际刷题过程中，建议大家多动手实践，理解解题思路的本质，这样才能更好地应对各种算法问题。