双指针
更新: 8/27/2025 字数: 0 字 时长: 0 分钟
移动零
java
/**
* <p>此方法使用一个额外数组，不满足原地操作的要求，但有助于理解逻辑。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li>创建一个与原数组大小相同的新数组 {@code result}，并默认填充 0。</li>
* <li>使用一个指针 {@code nonZeroIdx} 追踪 {@code result} 数组中下一个可放置非零元素的索引。</li>
* <li>遍历原数组 {@code nums}：
* <ul>
* <li>如果遇到非零元素，将其复制到 {@code result[nonZeroIdx]}，并递增 {@code nonZeroIdx}。</li>
* </ul>
* </li>
* <li>遍历结束后，{@code result} 数组的前半部分是非零元素（保持相对顺序），后半部分是 0。</li>
* <li>将 {@code result} 数组的内容复制回原数组 {@code nums}。</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)} - 遍历 {@code nums} 一次，然后复制 {@code result} 回 {@code nums} 一次。</li>
* <li><strong>空间复杂度：</strong> {@code O(n)} - 使用了一个与原数组大小相同的额外数组。</li>
* </ul>
*
* @param nums 输入的整数数组。
*/
public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int n = nums.length;
int[] result = new int[n]; // 创建一个新数组，默认元素为 0
int nonZeroIdx = 0; // 指向 result 数组中下一个非零元素应该放置的位置
// 遍历原数组，将所有非零元素按顺序填充到 result 数组的前面
for (int num : nums) {
if (num != 0) {
result[nonZeroIdx] = num;
nonZeroIdx++;
}
}
// 将 result 数组的内容复制回 nums 数组
// 由于 result 数组默认初始化为 0，并且 nonZeroIdx 之后的元素保持为 0，
// 这样就完成了将所有 0 移动到末尾的操作。
for (int i = 0; i < n; i++) {
nums[i] = result[i];
}
}java
/**
* <p>此方法使用双指针（{@code writePointer} 和 {@code readPointer}），在原地进行操作，不使用额外空间，满足题目要求。</p>
*
* <h3>算法思路（两阶段法）：</h3>
* <ol>
* <li><strong>阶段一：移动非零元素。</strong>
* <ul>
* <li>定义一个 {@code writePointer} (写入指针)，初始为 0。它指向数组中下一个非零元素应该放置的位置。</li>
* <li>定义一个 {@code readPointer} (读取指针)，初始为 0。它用于遍历数组 {@code nums} 中的所有元素。</li>
* <li>使用一个 {@code while} 循环，当 {@code readPointer} 未越界时：
* <ul>
* <li>如果当前元素 {@code nums[readPointer]} 是非零元素，将其复制到 {@code nums[writePointer]}，然后递增 {@code writePointer}。</li>
* <li>无论元素是否为零，都递增 {@code readPointer}，继续向后遍历。</li>
* </ul>
* </li>
* <li>此阶段结束后，数组的前 {@code writePointer} 个位置已经填充了所有非零元素，并且它们的相对顺序得以保持。而 {@code writePointer} 正好指向第一个 0 应该开始填充的位置。</li>
* </ul>
* </li>
* <li><strong>阶段二：填充剩余位置为零。</strong>
* <ul>
* <li>使用另一个 {@code while} 循环，从 {@code writePointer} 开始到数组的末尾，将所有元素都设置为 0。</li>
* <li>递增 {@code writePointer} 直到遍历完剩余所有位置。</li>
* <li>这些被填充为 0 的位置，要么原本就是 0，要么是被阶段一中的非零元素覆盖后，其原值（零）被移到了后面。</li>
* </ul>
* </li>
* </ol>
*
* <h3>优化关键点：</h3>
* <ul>
* <li><strong>原地操作：</strong> 不使用任何额外数组，直接在原数组上修改。</li>
* <li><strong>双指针：</strong> {@code readPointer} 负责高效地读取元素，{@code writePointer} 负责精确地写入非零元素，确保非零元素的相对顺序。</li>
* <li><strong>清晰的两阶段：</strong> 明确分离了“移动非零元素”和“填充零”两个职责，使得逻辑更易于理解和实现。</li>
* <li><strong>高效填充：</strong> 将非零元素集中到前面，然后一次性填充后面的零，避免了不必要的元素移动或交换操作。</li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}
* <ul>
* <li>第一个 {@code while} 循环（移动非零元素）：{@code readPointer} 从 0 到 {@code n-1} 遍历一次，{@code O(n)}。</li>
* <li>第二个 {@code while} 循环（填充零）：{@code writePointer} 从某个位置（最坏情况为 0，最好情况为 {@code n}）遍历到 {@code n-1}，最多 {@code O(n)}。</li>
* <li>总时间复杂度为 {@code O(n)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)} - 仅使用了常数个额外变量（两个指针）。</li>
* </ul>
*
* @param nums 输入的整数数组。
*/
public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
int n = nums.length;
int writePointer = 0; // writePointer 指向下一个非零元素应该写入的位置
int readPointer = 0; // readPointer 用于遍历数组，读取当前元素
// 阶段一：将所有非零元素移动到数组的前面，同时保持相对顺序
while (readPointer < n) {
if (nums[readPointer] != 0) {
nums[writePointer] = nums[readPointer];
writePointer++;
}
readPointer++; // readPointer 总是前进
}
// 阶段二：从 writePointer 开始，将数组的剩余部分填充为 0
// 此时 writePointer 指向第一个 0 应该放置的位置
while (writePointer < n) {
nums[writePointer] = 0;
writePointer++; // 填充下一个 0
}
}java
/**
* <p>此方法采用双指针（{@code left} 和 {@code right}）和交换策略进行原地操作，不使用额外空间。</p>
*
* <h3>算法思路（双指针交换法）：</h3>
* <ol>
* <li><strong>定义双指针：</strong>
* <ul>
* <li>{@code left} 指针：始终指向当前第一个 0 元素的位置（或即将放置非零元素的位置）。它将用于与 {@code right} 指针指向的非零元素进行交换。</li>
* <li>{@code right} 指针：负责遍历整个数组，寻找非零元素。</li>
* </ul>
* </li>
* <li><strong>遍历与交换：</strong>
* <ul>
* <li>当 {@code right} 指针遍历数组时：
* <ul>
* <li>如果 {@code nums[right]} 是<strong>非零元素</strong>：
* <ul>
* <li>这意味着我们找到了一个非零元素，它需要被移动到 {@code left} 指针指向的位置（该位置要么是 0，要么是其自身）。</li>
* <li>执行交换操作，将 {@code nums[right]} 处的非零元素与 {@code nums[left]} 处的元素交换。</li>
* <li>然后将 {@code left} 指针向右移动一位，准备寻找下一个需要放置非零元素的位置。</li>
* </ul>
* </li>
* <li>如果 {@code nums[right]} 是<strong>零元素</strong>：
* <ul>
* <li>不需要进行交换，因为我们希望 0 留在后面。</li>
* <li>{@code left} 指针保持不变，继续指向当前或之前的 0。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li>无论 {@code nums[right]} 是零还是非零，{@code right} 指针都会向右移动一位，继续遍历数组。</li>
* </ul>
* </li>
* <li><strong>最终状态：</strong> 当 {@code right} 遍历完整个数组后，所有非零元素都被移动到了数组的前部（通过交换操作），并且它们的相对顺序得以保持。而所有 0 都被“推”到了数组的末尾。</li>
* </ol>
*
* <h3>优化关键点：</h3>
* <ul>
* <li><strong>原地操作：</strong> 不使用任何额外数组，直接在原数组上修改。</li>
* <li><strong>双指针策略：</strong> 通过 {@code left} 和 {@code right} 两个指针协同工作，{@code right} 负责寻找非零元素，{@code left} 负责标记非零元素应该放置的位置。</li>
* <li><strong>保持相对顺序：</strong> 只有当 {@code nums[right]} 是非零元素时才进行交换，且 {@code left} 总是小于或等于 {@code right}，确保非零元素之间的相对顺序不会改变。</li>
* <li><strong>避免不必要的交换：</strong> 当 {@code nums[right]} 为零时，{@code left} 不动，{@code right} 继续前进，有效地将零跳过。当 {@code nums[right]} 非零且 {@code left == right} 时，虽然也执行了交换，但实际上是自己与自己交换，没有改变值，只是形式上保持了逻辑一致性。</li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}
* <ul>
* <li>两个指针都只遍历数组一次（{@code right} 完整遍历，{@code left} 最多移动 {@code n} 次）。</li>
* <li>每次遍历中的操作（比较、交换）都是常数时间操作。</li>
* <li>因此，总时间复杂度为 {@code O(n)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)} - 仅使用了常数个额外变量（指针和交换时的临时变量）。</li>
* </ul>
*
* @param nums 输入的整数数组。
*/
public void moveZeroes(int[] nums) {
int n = nums.length;
int left = 0; // left 指针，指向当前第一个 0 出现的位置，或下一个非零元素应放置的位置
int right = 0; // right 指针，用于遍历数组，寻找非零元素
// 当 right 指针没有越界时，持续遍历
while (right < n) {
// 如果 right 指针指向的元素是非零元素
if (nums[right] != 0) {
// 将 nums[right]（非零元素）与 nums[left] 处的元素进行交换
// 这样就把非零元素移到了前面，同时把 0 移到了后面（或非零元素自身位置）
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++; // left 指针向右移动，准备放置下一个非零元素
}
right++; // right 指针总是向右移动，继续寻找
}
}盛最多水的容器
java
/**
* <p>此方法通过暴力枚举所有可能的蓄水区域组合来找到最大面积。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li>初始化 {@code maxArea} 为 0，用于记录找到的最大蓄水面积。</li>
* <li>使用一个外层循环，由指针 {@code left} 从数组的起始位置 {@code 0} 遍历到 {@code n-2}（因为 {@code right} 至少比 {@code left} 大 1）。{@code left} 代表左边界的高度。</li>
* <li>在每次外层循环中，使用一个内层循环，由指针 {@code right} 从数组的末尾位置 {@code n-1} 遍历到 {@code left + 1}。{@code right} 代表右边界的高度。</li>
* <li>对于每一对 {@code (left, right)}，计算当前蓄水区域的面积：
* <ul>
* <li>高度由两个边界中较矮的那个决定：{@code Math.min(height[left], height[right])}。</li>
* <li>宽度是两个边界之间的距离：{@code right - left}。</li>
* <li>当前面积 {@code currentArea = Math.min(height[left], height[right]) * (right - left)}。</li>
* </ul>
* </li>
* <li>将 {@code currentArea} 与 {@code maxArea} 比较，更新 {@code maxArea = Math.max(maxArea, currentArea)}。</li>
* <li>内层循环结束后，递增 {@code left}，继续寻找下一个可能的左边界。</li>
* <li>所有组合遍历完毕后，返回 {@code maxArea}。</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n^2)} - 外层循环执行 {@code n-1} 次，内层循环平均执行 {@code n/2} 次，导致嵌套循环的总操作次数近似于 {@code n * n/2}。</li>
* <li><strong>空间复杂度：</strong> {@code O(1)} - 仅使用了常数个额外变量。</li>
* </ul>
*
* @param height 一个整数数组，其中 {@code height[i]} 表示坐标 {@code (i, 0)} 处的垂直线的高度。
* @return 能够容纳的最大水量。
*/
public int maxArea(int[] height) {
int n = height.length;
int left = 0;
int maxArea = 0;
// 外层循环：固定左边界
while (left < n) {
// 内层循环：从右向左移动右边界，与固定左边界形成所有可能的组合
int right = n - 1;
while (left < right) {
// 计算当前容器的面积
int currentArea = Math.min(height[left], height[right]) * (right - left);
// 更新最大面积
maxArea = Math.max(maxArea, currentArea);
// 移动右边界向左，尝试下一个组合
right--;
}
// 移动左边界向右，开始新一轮的右边界组合
left++;
}
return maxArea;
}java
/**
* <p>此方法使用双指针（{@code left} 和 {@code right}）技术，以线性时间复杂度找到能够容纳最大水量的容器。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li>初始化两个指针：{@code left} 指向数组的起始位置 {@code 0}，{@code right} 指向数组的末尾位置 {@code n-1}。</li>
* <li>初始化 {@code maxArea} 为 0，用于记录找到的最大蓄水面积。</li>
* <li>使用一个 {@code while} 循环，条件是 {@code left < right}，表示左右指针尚未相遇。</li>
* <li>在每次循环中，计算当前由 {@code left} 和 {@code right} 构成的容器的面积：
* <ul>
* <li>高度由两个边界中较矮的那个决定：{@code h = Math.min(height[left], height[right])}。</li>
* <li>宽度是两个边界之间的距离：{@code w = right - left}。</li>
* <li>当前面积 {@code currentArea = h * w}。</li>
* </ul>
* </li>
* <li>将 {@code currentArea} 与 {@code maxArea} 比较，更新 {@code maxArea = Math.max(maxArea, currentArea)}。</li>
* <li><strong>移动策略（核心优化）：</strong>为了寻找更大的面积，我们需要尝试增加容器的高度或宽度。
* <ul>
* <li>由于宽度 {@code (right - left)} 在每次迭代中必然减小（因为指针会向内移动），所以我们必须尝试增加高度来弥补。</li>
* <li>关键观察：移动较高边界不会增加容器的高度（因为它受限于较矮边界），但会减少宽度。因此，为了潜在地找到更大的面积，我们应该移动<strong>较矮的那个边界</strong>。
* <ul>
* <li>如果 {@code height[left] < height[right]}，说明左边界是当前较矮的，移动 {@code left++}。</li>
* <li>否则，说明右边界是当前较矮的或两者相等，移动 {@code right--}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li>循环继续，直到 {@code left} 和 {@code right} 相遇，此时所有可能的有效容器都已被考虑。</li>
* <li>返回最终的 {@code maxArea}。</li>
* </ol>
*
* <h3>优化关键点：</h3>
* <ul>
* <li><strong>双指针：</strong> 从两端开始向中间收敛，避免了暴力法的冗余计算。</li>
* <li><strong>贪心策略：</strong> 每一步都选择移动较矮的那个边界，这是因为：
* <ul>
* <li>如果移动高的一边，容器高度将仍然受限于矮的一边，而宽度必然减小，面积不可能增大。</li>
* <li>只有移动矮的一边，才有可能遇到一个更高的高度，从而有机会形成更大的容器面积（即使宽度减小了）。</li>
* </ul>
* </li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)} - 两个指针 {@code left} 和 {@code right} 总共遍历数组一次（或者说，它们之间的距离每次减少至少 1，直到相遇），因此循环执行的次数与数组长度成正比。</li>
* <li><strong>空间复杂度：</strong> {@code O(1)} - 仅使用了常数个额外变量（两个指针和 {@code maxArea}）。</li>
* </ul>
*
* @param height 一个整数数组，其中 {@code height[i]} 表示坐标 {@code (i, 0)} 处的垂直线的高度。
* @return 能够容纳的最大水量。
*/
public int maxArea(int[] height) {
int n = height.length;
int left = 0; // 左指针
int right = n - 1; // 右指针
int maxArea = 0; // 记录最大面积
// 当左指针在右指针的左边时，继续计算
while (left < right) {
// 计算当前容器的面积：较短的高度 * 宽度
int currentArea = Math.min(height[left], height[right]) * (right - left);
// 更新最大面积
maxArea = Math.max(maxArea, currentArea);
// 根据左右边界的高度，移动较矮的那个指针
// 这是算法的关键优化点：移动较矮的边界才有可能找到更大的面积
if (height[left] < height[right]) {
left++; // 左边界较矮，向右移动左指针
} else {
right--; // 右边界较矮或两者相等，向左移动右指针
}
}
return maxArea;
}三数之和
java
/**
* <p>此方法通过三重循环暴力枚举所有可能的三元组，然后检查它们的和是否为 0。</p>
* <p>为了处理重复的三元组，使用了 {@link HashSet} 来存储已经找到的唯一三元组。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li>初始化一个 {@code Set<List<Integer>>} 来存储不重复的三元组。使用 {@code Set} 是为了自动去重。</li>
* <li>进行三重嵌套循环：
* <ul>
* <li>外层循环 {@code i} 从 {@code 0} 到 {@code n-3}。</li>
* <li>中层循环 {@code j} 从 {@code i+1} 到 {@code n-2}。</li>
* <li>内层循环 {@code k} 从 {@code j+1} 到 {@code n-1}。</li>
* </ul>
* </li>
* <li>在内层循环中，检查 {@code nums[i] + nums[j] + nums[k] == 0} 是否成立。</li>
* <li>如果和为 0：
* <ul>
* <li>创建一个新的 {@code List<Integer>} 包含 {@code nums[i], nums[j], nums[k]}。</li>
* <li><strong>为了确保三元组的唯一性（例如 [-1,0,1] 和 [0,-1,1] 算作同一个），需要先对这个临时列表进行排序。</strong></li>
* <li>将排序后的列表添加到 {@code Set} 中。</li>
* </ul>
* </li>
* <li>循环结束后，将 {@code Set} 中的所有三元组转换成 {@code List<List<Integer>>} 并返回。</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n^3 * log(3))}。
* <ul>
* <li>三重嵌套循环导致 {@code O(n^3)} 的基本操作。</li>
* <li>每次找到符合条件的三元组时，需要对其进行排序 ({@code O(log(3))} 是常数时间) 并添加到 {@code HashSet} 中。{@code HashSet} 的 {@code add} 操作平均是 {@code O(1)}，最坏是 {@code O(k)} (k 为元素个数)，这里是常数 3。</li>
* <li>总体上，时间复杂度由三重循环主导，为 {@code O(n^3)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(m * 3)}，其中 {@code m} 是符合条件的不重复三元组的数量。
* <ul>
* <li>用于存储结果的 {@code HashSet} 最坏情况下会存储 {@code O(n^3)} 个三元组（虽然实际中通常少得多），每个三元组占用 {@code O(3)} 空间。</li>
* <li>在最坏情况下，如果所有三元组都不同，空间复杂度可能接近 {@code O(n^3)}。</li>
* </ul>
* </li>
* </ul>
*
* @param nums 输入的整数数组。
* @return 所有和为 0 且不重复的三元组。
*/
public List<List<Integer>> threeSum(int[] nums) {
Set<List<Integer>> resultSet = new HashSet<>();
int n = nums.length;
// 如果数组长度小于 3，不可能找到三元组
if (n < 3) {
return new ArrayList<>(resultSet);
}
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
// 使用 Arrays.asList() 将三个整数快速封装成一个不可变的 List
List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]);
// 为了确保三元组的唯一性，先对内部元素排序
// 例如 [-1,0,1] 和 [0,-1,1] 排序后都是 [-1,0,1]
// 使用 null 作为比较器，表示使用元素的自然排序顺序（对于 Integer 就是数值大小）
triplet.sort(null);
resultSet.add(triplet);
}
}
}
}
// 将 Set 中收集到的所有唯一三元组转换成 List 返回
return new ArrayList<>(resultSet);
}java
/**
* <p>此方法通过排序数组和双指针技术来高效地找到所有和为 0 且不重复的三元组。</p>
* <p>它是解决三数之和问题的标准优化方法。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li><strong>排序数组：</strong> 首先对输入的数组 {@code nums} 进行排序。这是双指针方法能够奏效的关键前提，因为它允许我们有序地处理元素并有效地跳过重复项。</li>
* <li><strong>遍历固定第一个数：</strong> 使用一个外层循环，固定第一个数 {@code nums[i]}。
* <ul>
* <li>这个循环从 {@code 0} 遍历到 {@code n-3}（因为后面还需要至少两个数）。</li>
* <li><strong>去重 {@code i}：</strong> 为了避免结果中出现重复的三元组，如果 {@code nums[i]} 和 {@code nums[i-1]} 相等，则跳过当前的 {@code i}。这确保了我们不会重复处理相同的第一个数。</li>
* <li><strong>剪枝优化：</strong>
* <ul>
* <li>如果 {@code nums[i] > 0}，由于数组已排序，后续的数都大于等于 {@code nums[i]}，因此它们的和不可能为 0。直接中断外层循环。</li>
* <li>（可选）如果 {@code nums[i] + nums[i+1] + nums[i+2] > 0}，即当前数和后面两个最小的数加起来都大于 0，那么再往后也不可能找到和为 0 的了，直接中断循环。</li>
* <li>（可选）如果 {@code nums[i] + nums[n-1] + nums[n-2] < 0}，即当前数和后面两个最大的数加起来都小于 0，那么当前的 {@code nums[i]} 太小了，需要增大 {@code i}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>使用双指针寻找后两个数：</strong> 在外层循环中，对于每个固定的 {@code nums[i]}，使用两个指针 {@code left} 和 {@code right} 在 {@code (i+1, n-1)} 的范围内寻找另外两个数。
* <ul>
* <li>{@code left} 指针初始值为 {@code i+1}。</li>
* <li>{@code right} 指针初始值为 {@code n-1}。</li>
* <li>在内层 {@code while (left < right)} 循环中执行以下操作：
* <ul>
* <li>计算当前三数之和 {@code sum = nums[i] + nums[left] + nums[right]}。</li>
* <li>如果 {@code sum == 0}：
* <ul>
* <li>找到一个有效的三元组，将其添加到结果列表 {@code result} 中。</li>
* <li><strong>去重 {@code left} 和 {@code right}：</strong> 为了避免结果中出现重复的三元组，在找到一个有效三元组后，继续移动 {@code left} 指针，直到它指向的元素与前一个不同；同样地，移动 {@code right} 指针，直到它指向的元素与前一个不同。</li>
* <li>然后，{@code left++} 和 {@code right--}，继续寻找下一个可能的三元组。</li>
* </ul>
* </li>
* <li>如果 {@code sum < 0}：
* <ul>
* <li>和太小，需要增大。由于数组已排序，我们通过移动 {@code left++} 来增大和。</li>
* </ul>
* </li>
* <li>如果 {@code sum > 0}：
* <ul>
* <li>和太大，需要减小。通过移动 {@code right--} 来减小和。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li>所有循环结束后，返回结果列表 {@code result}。</li>
* </ol>
*
* <h3>关键优化点：</h3>
* <ul>
* <li><strong>排序：</strong> 将问题从无序数组的搜索转化为有序数组的双指针搜索。</li>
* <li><strong>去重：</strong> 通过在移动指针时跳过与前一个元素相同的元素，有效避免了结果中重复的三元组。</li>
* <li><strong>剪枝：</strong> 提前判断某些情况下不可能找到解决方案，从而减少不必要的计算。</li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n^2)}。
* <ul>
* <li>排序数组需要 {@code O(n log n)}。</li>
* <li>外层循环执行 {@code O(n)} 次。</li>
* <li>内层双指针循环（{@code left} 和 {@code right}）在每次外层循环中总共移动 {@code O(n)} 次。</li>
* <li>因此，总时间复杂度为 {@code O(n log n + n * n)}，简化为 {@code O(n^2)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(log n)} 或 {@code O(n)}。
* <ul>
* <li>如果排序算法使用原地排序（如堆排序），则空间复杂度为 {@code O(log n)}（取决于递归栈深度）。</li>
* <li>如果排序算法需要额外空间（如归并排序），则空间复杂度为 {@code O(n)}。</li>
* <li>结果列表 {@code result} 的空间取决于找到的不重复三元组的数量，最坏情况下可能接近 {@code O(n^3)}，但在实际竞赛题目中，通常不将其计入算法本身的额外空间复杂度，或者说假设其为 {@code O(n)} 级别的结果存储。</li>
* </ul>
* </li>
* </ul>
*
* @param nums 输入的整数数组。
* @return 所有和为 0 且不重复的三元组。
*/
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
// 1. 如果数组长度小于 3，不可能找到三元组
if (n < 3) {
return result;
}
// 2. 排序数组，这是双指针法的基础
Arrays.sort(nums);
// 3. 遍历数组，固定第一个数 nums[i]
// i 只需要遍历到 n-3，因为后面还需要两个数
for (int i = 0; i < n - 2; i++) {
// 优化 1: 如果 nums[i] 已经大于 0，由于数组已排序，
// 后面两个数都 >= nums[i]，它们的和不可能为 0 了，直接退出
if (nums[i] > 0) {
break;
}
// 优化 2: 去重 nums[i]
// 如果当前的 nums[i] 和前一个 nums[i-1] 相同，
// 那么以 nums[i] 开头的三元组在 i-1 的迭代中已经处理过了，跳过
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 4. 使用双指针 left 和 right 在 (i+1, n-1) 范围内寻找另外两个数
int left = i + 1;
int right = n - 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]));
// 优化 3: 去重 left 和 right 指针指向的元素
// 移动 left 指针，直到它指向的元素与前一个不同
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
// 移动 right 指针，直到它指向的元素与前一个不同
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
// 继续向内移动指针，寻找下一个可能的三元组
left++;
right--;
} else if (sum < 0) {
// 和太小，需要增大，移动 left 指针
left++;
} else { // sum > 0
// 和太大，需要减小，移动 right 指针
right--;
}
}
}
return result;
}接雨水
java
/**
* <p>此方法使用双指针（{@code left} 和 {@code right}）技术，以线性时间复杂度和常数空间复杂度解决接雨水问题。</p>
* <p>它结合了动态规划的思想，但在不额外存储左右最高高度数组的情况下实现了同样的效果。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li>初始化两个指针：{@code left} 指向数组的起始位置 {@code 0}，{@code right} 指向数组的末尾位置 {@code n-1}。</li>
* <li>初始化 {@code totalWater = 0}。</li>
* <li>维护两个变量：{@code maxLeft} 记录 {@code height[0...left]} 的最大高度，{@code maxRight} 记录 {@code height[right...n-1]} 的最大高度。
* <ul>
* <li>初始时，{@code maxLeft = height[0]}，{@code maxRight = height[n-1]}。</li>
* </ul>
* </li>
* <li>使用一个 {@code while (left < right)} 循环，直到两个指针相遇。</li>
* <li>在每次循环中，根据左右边界的最大高度来决定移动哪个指针：
* <ul>
* <li><strong>如果 {@code maxLeft < maxRight}：</strong>
* <ul>
* <li>这意味着当前计算雨水时，右侧的边界更高或相等，因此左侧的 {@code maxLeft} 是瓶颈。</li>
* <li>我们确定当前位置 {@code left} 能接到的雨水高度只受限于 {@code maxLeft}。</li>
* <li>移动 {@code left++}。</li>
* <li>在移动前，先更新 {@code maxLeft = Math.max(maxLeft, height[left])}。</li>
* <li>计算当前位置 {@code left}（移动后的新位置）能接的雨水：{@code totalWater += maxLeft - height[left]}。
* <p>注意：这里的 {@code maxLeft} 是指到 {@code left} 为止的左侧最高，而不是 {@code height[left]} 自身。在更新 {@code maxLeft} 之后，它已经包含了当前 {@code height[left]} 的值。</p></li>
* </ul>
* </li>
* <li><strong>否则（{@code maxRight <= maxLeft}）：</strong>
* <ul>
* <li>这意味着当前计算雨水时，左侧的边界更高或相等，因此右侧的 {@code maxRight} 是瓶颈。</li>
* <li>我们确定当前位置 {@code right} 能接到的雨水高度只受限于 {@code maxRight}。</li>
* <li>移动 {@code right--}。</li>
* <li>在移动前，先更新 {@code maxRight = Math.max(maxRight, height[right])}。</li>
* <li>计算当前位置 {@code right}（移动后的新位置）能接的雨水：{@code totalWater += maxRight - height[right]}。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li>循环结束后，返回 {@code totalWater}。</li>
* </ol>
*
* <h3>核心思想：</h3>
* <p>在双指针 {@code left} 和 {@code right} 移动过程中，始终维护 {@code maxLeft} (左指针左侧的最大高度) 和 {@code maxRight} (右指针右侧的最大高度)。</p>
* <ul>
* <li>当 {@code maxLeft < maxRight} 时，我们知道当前 {@code left} 指针位置能接的雨水高度，只取决于 {@code maxLeft}。因为即使 {@code height[left]} 右侧有更高的墙，其高度也受限于 {@code maxRight} (此时 {@code maxRight >= maxLeft})。所以我们只需要考虑左侧的最高墙。</li>
* <li>反之，当 {@code maxRight <= maxLeft} 时，同理，当前 {@code right} 指针位置能接的雨水高度，只取决于 {@code maxRight}。</li>
* </ul>
* <p>这种方法避免了预先计算整个 {@code maxLeft} 和 {@code maxRight} 数组，而是实时更新和使用局部最大值。</p>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>两个指针 {@code left} 和 {@code right} 总共遍历数组一次（它们之间的距离每次减少至少 1，直到相遇）。</li>
* <li>每次迭代中的操作都是常数时间。</li>
* <li>总时间复杂度为 {@code O(n)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(1)}。
* <ul>
* <li>仅使用了常数个额外变量（两个指针和两个最大高度记录）。</li>
* </ul>
* </li>
* </ul>
*
* @param height 一个整数数组，表示每个宽度为 1 的柱子的高度。
* @return 能够接到的雨水总量。
*/
public int trap(int[] height) {
int n = height.length;
if (n <= 2) {
return 0;
}
int left = 0;
int right = n - 1;
int totalWater = 0;
int maxLeft = 0; // 记录 left 指针左侧（包括 left 自身）的最高高度
int maxRight = 0; // 记录 right 指针右侧（包括 right 自身）的最高高度
// 两个指针相向而行
while (left < right) {
// 实时更新 maxLeft 和 maxRight
maxLeft = Math.max(maxLeft, height[left]);
maxRight = Math.max(maxRight, height[right]);
// 哪个指针指向的“局部”最大值较小，就移动哪个指针
// 因为较小的那一侧决定了当前水位的上限
if (maxLeft < maxRight) {
// 如果左边最大值更小，说明当前 left 位置能接的水的高度受限于 maxLeft
// 此时，maxRight 已经保证大于等于 maxLeft，所以右边的边界足够高
totalWater += maxLeft - height[left];
left++;
} else {
// 如果右边最大值更小或相等，说明当前 right 位置能接的水的高度受限于 maxRight
// 此时，maxLeft 已经保证大于等于 maxRight，所以左边的边界足够高
totalWater += maxRight - height[right];
right--;
}
}
return totalWater;
}java
/**
* <p>此方法使用单调递减栈来计算雨水。单调栈能有效地找到当前元素左侧第一个比它大的元素。</p>
* <p>当遇到一个比栈顶元素高的柱子时，意味着形成了一个"凹槽"，可以计算并累加中间的雨水。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li>初始化一个空栈 {@code stack}，用于存储柱子的索引。栈中元素将保持单调递减（从栈底到栈顶）。</li>
* <li>初始化 {@code totalWater = 0}。</li>
* <li>遍历数组 {@code height}，从左到右，索引为 {@code i}：
* <ul>
* <li>当栈不为空且当前柱子 {@code height[i]} <strong>大于</strong>栈顶柱子 {@code height[stack.peek()]} 时：
* <ul>
* <li>说明找到了一个"凹槽"的右边界 {@code i}。</li>
* <li>弹出栈顶元素 {@code bottomIdx}，它代表了凹槽的底部。</li>
* <li>如果栈仍然不为空（即存在左边界）：
* <ul>
* <li>左边界索引为 {@code leftIdx = stack.peek()}。</li>
* <li>凹槽的高度由 {@code Math.min(height[i], height[leftIdx])} 决定，减去底部高度 {@code height[bottomIdx]}。</li>
* <li>凹槽的宽度为 {@code i - leftIdx - 1}。</li>
* <li>计算并累加雨水：{@code totalWater += (Math.min(height[i], height[leftIdx]) - height[bottomIdx]) * (i - leftIdx - 1)}。</li>
* </ul>
* </li>
* <li>重复此过程，直到栈为空或者当前柱子不再大于栈顶柱子。</li>
* </ul>
* </li>
* <li>将当前柱子的索引 {@code i} 压入栈中。</li>
* </ul>
* </li>
* <li>遍历结束后，返回 {@code totalWater}。</li>
* </ol>
*
* <h3>核心思想：</h3>
* <p>单调栈维护一个递减的柱子索引序列。当遍历到当前柱子 {@code height[i]} 时：</p>
* <ul>
* <li>如果 {@code height[i]} 小于或等于栈顶柱子：直接入栈，保持递减趋势。它可能成为未来某个凹槽的左边界。</li>
* <li>如果 {@code height[i]} 大于栈顶柱子：
* <ul>
* <li>弹出栈顶柱子（{@code bottomIdx}），它是一个局部凹陷的底部。</li>
* <li>此时，如果栈不为空，那么新的栈顶柱子就是这个凹陷的左边界（{@code leftIdx}），当前柱子 {@code height[i]} 是右边界。</li>
* <li>利用 {@code height[leftIdx]}、{@code height[bottomIdx]} 和 {@code height[i]} 以及它们的索引来计算接到的雨水。</li>
* <li>重复此过程，直到栈为空或当前柱子不再大于栈顶。</li>
* </ul>
* </li>
* </ul>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>每个元素最多被压入栈一次，弹出栈一次。</li>
* <li>栈操作（push, pop, peek）都是 {@code O(1)}。</li>
* <li>总时间复杂度为 {@code O(n)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>在最坏情况下（例如，柱子高度递减），栈会存储所有元素的索引。</li>
* <li>因此，空间复杂度为 {@code O(n)}。</li>
* </ul>
* </li>
* </ul>
*
* @param height 一个整数数组，表示每个宽度为 1 的柱子的高度。
* @return 能够接到的雨水总量。
*/
public int trap(int[] height) {
int n = height.length;
if (n <= 2) {
return 0;
}
Stack<Integer> stack = new Stack<>(); // 存储柱子索引，保持栈中元素所代表的柱子高度单调递减
int totalWater = 0;
for (int i = 0; i < n; i++) {
// 当栈不为空，并且当前柱子高度大于栈顶柱子高度时
// 说明找到了一个“凹槽”的右边界
while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
int bottomIdx = stack.pop(); // 弹出凹槽的底部柱子索引
// 如果栈为空，说明左侧没有更高的柱子作为边界，无法形成有效凹槽
if (stack.isEmpty()) {
break;
}
int leftIdx = stack.peek(); // 凹槽的左边界柱子索引
int h = Math.min(height[i], height[leftIdx]) - height[bottomIdx]; // 凹槽有效高度
int w = i - leftIdx - 1; // 凹槽宽度
totalWater += h * w;
}
stack.push(i); // 将当前柱子索引压入栈中
}
return totalWater;
}java
/**
* <p>此方法使用动态规划计算每个位置能接的雨水量，然后累加得到总雨水。</p>
* <p>核心思想是对于每个位置 {@code i}，其能接的雨水高度取决于它左右两侧的最高柱子的高度中的较小值，再减去当前柱子的高度。</p>
* <p>即 {@code water[i] = min(max_left[i], max_right[i]) - height[i]}。</p>
*
* <h3>算法思路：</h3>
* <ol>
* <li><strong>预处理左侧最高高度：</strong>
* <ul>
* <li>创建一个数组 {@code maxLeft}，{@code maxLeft[i]} 存储 {@code height[0...i]} 中最高的柱子高度。</li>
* <li>初始化 {@code maxLeft[0] = height[0]}。</li>
* <li>从左到右遍历数组：{@code maxLeft[i] = Math.max(maxLeft[i-1], height[i])}。</li>
* </ul>
* </li>
* <li><strong>预处理右侧最高高度：</strong>
* <ul>
* <li>创建一个数组 {@code maxRight}，{@code maxRight[i]} 存储 {@code height[i...n-1]} 中最高的柱子高度。</li>
* <li>初始化 {@code maxRight[n-1] = height[n-1]}。</li>
* <li>从右到左遍历数组：{@code maxRight[i] = Math.max(maxRight[i+1], height[i])}。</li>
* </ul>
* </li>
* <li><strong>计算总雨水：</strong>
* <ul>
* <li>初始化 {@code totalWater = 0}。</li>
* <li>遍历数组从 {@code 0} 到 {@code n-1} 的每个位置 {@code i}：
* <ul>
* <li>当前位置能接的雨水高度为 {@code Math.min(maxLeft[i], maxRight[i]) - height[i]}。</li>
* <li>如果计算结果大于 0（即当前柱子低于左右两侧最高柱子的较小值），则将其加到 {@code totalWater} 中。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li>返回 {@code totalWater}。</li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>计算 {@code maxLeft} 数组需要一次遍历：{@code O(n)}。</li>
* <li>计算 {@code maxRight} 数组需要一次遍历：{@code O(n)}。</li>
* <li>计算总雨水需要一次遍历：{@code O(n)}。</li>
* <li>总时间复杂度为 {@code O(n + n + n) = O(n)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>需要额外的 {@code maxLeft} 数组和 {@code maxRight} 数组，每个数组的大小为 {@code n}。</li>
* <li>总空间复杂度为 {@code O(n + n) = O(n)}。</li>
* </ul>
* </li>
* </ul>
*
* @param height 一个整数数组，表示每个宽度为 1 的柱子的高度。
* @return 能够接到的雨水总量。
*/
public int trap(int[] height) {
int n = height.length;
if (n <= 2) { // 至少需要 3 个柱子才能接住雨水
return 0;
}
// maxLeft[i] 存储 height[0...i] 中的最大高度
int[] maxLeft = new int[n];
maxLeft[0] = height[0];
for (int i = 1; i < n; i++) {
maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
}
// maxRight[i] 存储 height[i...n-1] 中的最大高度
int[] maxRight = new int[n];
maxRight[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) {
maxRight[i] = Math.max(maxRight[i + 1], height[i]);
}
int totalWater = 0;
// 计算每个位置能接的雨水并累加
for (int i = 0; i < n; i++) {
// 当前位置能接的雨水高度 = min(左边最高，右边最高) - 当前柱子高度
int waterAtI = Math.min(maxLeft[i], maxRight[i]) - height[i];
if (waterAtI > 0) { // 只有当结果大于 0 时才表示能接水
totalWater += waterAtI;
}
}
return totalWater;
}贡献者
LI SIR