Dorian's Blog

双指针

1 移动零

【原始题目】

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

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

示例 1:

输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]

示例 2:

输入: nums = [0] 输出: [0]

提示:

1 <= nums.length <= 10^4
-2^31 <= nums[i] <= 2^31 - 1

进阶： 你能尽量减少完成的操作次数吗？

【题目速记】

给定一个整数数组，把所有 0 挪到末尾，非零元素保持原来的相对顺序。必须原地操作，不能复制数组。尽量减少操作次数。

【题解】

一句话速通：用双指针从左向右扫描，慢指针指向下个非零元素应该放置的位置，快指针遍历数组，遇到非零就交换到慢指针位置，一次遍历完成。

【算法思想】

双指针：快指针 fast 遍历数组，慢指针 slow 记录已处理好的非零区域的下一个位置；通过交换将非零元素前移，零自然被挤到后面。
原地交换：利用数组下标直接交换元素，无需额外空间。

【核心思路】

初始化慢指针 $slow = 0$，表示下一个非零元素应该放的位置。
快指针 $fast$ 从 $0$ 遍历到 $n-1$：
- 如果 $nums[fast] \neq 0$，则交换 $nums[slow]$ 与 $nums[fast]$，然后 $slow$ 右移一位。
遍历结束时，所有非零元素已按顺序移到前面，零都在后面，操作次数等于非零元素个数。

【复杂度】

时间复杂度 $O(n)$ ：只遍历一遍数组。
空间复杂度 $O(1)$ ：原地操作，只用了两个指针变量。

【伪代码】

text

slow = 0
for fast from 0 to n-1:
    if nums[fast] != 0:
        swap(nums[slow], nums[fast])
        slow = slow + 1

【易错点】

交换时如果 $slow == fast$，自己与自己交换没问题，但注意不要跳过 slow 的递增，否则后续元素无法前移。
当数组全部为非零时，slow 和 fast 同步移动，每次自己和自己交换，结果是原数组不变，正确。
不要用“先覆盖再补零”的思路而引发额外写操作，此解法最小化交换次数。

【完整代码】

Java

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        for (int fast = 0; fast &lt; nums.length; fast++) {
            if (nums[fast] != 0) {
                // 交换 nums[slow] 和 nums[fast]
                int temp = nums[slow];
                nums[slow] = nums[fast];
                nums[fast] = temp;
                slow++;
            }
        }
    }
}

【题解】

一句话速通：先遍历一次数组，把所有非零元素按顺序覆盖到数组前面，再在剩余位置补零，完成原地移动。

【算法思想】

双指针（读写指针）：一个指针 insertPos 记录下一个非零元素应该覆盖的位置，另一个指针 i 扫描原数组；本质是“覆盖 + 填充”两步。
原地修改：覆盖操作在同一个数组上进行，不产生新数组。

【核心思路】

定义 insertPos = 0，表示非零元素要放入的位置。
遍历数组，若 nums[i] != 0，则 nums[insertPos] = nums[i]，insertPos++。
遍历结束后，insertPos 指向第一个应该为零的位置；从 insertPos 到数组末尾全部赋值为 $0$ 。

【复杂度】

时间复杂度 $O(n)$ ：遍历两次（一次复制非零，一次补零），两次线性扫描。
空间复杂度 $O(1)$ ：原地操作。

【伪代码】

text

insertPos = 0
for i from 0 to n-1:
    if nums[i] != 0:
        nums[insertPos] = nums[i]
        insertPos = insertPos + 1

while insertPos &lt; n:
    nums[insertPos] = 0
    insertPos = insertPos + 1

【易错点】

覆盖时原位置的元素会被破坏，但非零元素已保存到前面，不影响最终结果。
补零循环的起点是 insertPos，必须保证 insertPos 停留在正确位置（第一个待补零的位置）。
如果数组中没有零，则 insertPos 会走到 n，补零循环不会执行，结果正确。

【完整代码】

Java

class Solution {
    public void moveZeroes(int[] nums) {
        int insertPos = 0;
        // 把所有非零元素按顺序移到前面
        for (int i = 0; i &lt; nums.length; i++) {
            if (nums[i] != 0) {
                nums[insertPos] = nums[i];
                insertPos++;
            }
        }
        // 剩余位置补零
        while (insertPos &lt; nums.length) {
            nums[insertPos] = 0;
            insertPos++;
        }
    }
}

2 盛最多水的容器

【原始题目】

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

说明：你不能倾斜容器。
n == height.length，2 <= n <= 10^5，0 <= height[i] <= 10^4。

【题目速记】

数组下标代表横坐标，数值代表柱子高度。选两根柱子，和 x 轴围成一个容器，容量 = 下标距离 × 两柱较矮高度。求所有可能组合中的最大容量。

【题解】

一句话速通：枚举所有左右柱子组合，计算当前容量并更新最大值，双重循环暴力求解。

【算法思想】

暴力枚举：穷举所有可能的左柱和右柱组合
最值维护：用一个变量滚动记录遍历过程中的最大面积

【核心思路】

初始化最大值变量 ans = 0
外层循环左指针 i 从 0 到 n-2
内层循环右指针 j 从 i+1 到 n-1
当前面积 = (j - i) × min(height[i], height[j])
用 ans = max(ans, 当前面积) 更新答案
循环结束返回 ans

【复杂度】

时间复杂度 $O(n^2)$ ：两重循环枚举所有数对
空间复杂度 $O(1)$ ：只使用了常数个临时变量

【伪代码】

text

ans = 0
for i = 0 to n-2:
    for j = i+1 to n-1:
        area = (j - i) * min(height[i], height[j])
        ans = max(ans, area)
return ans

【易错点】

j 必须从 i+1 开始，避免同一根柱子和自己组成容器以及重复枚举
面积公式要用 (j - i)，别写成 (j - i + 1)
两个高度取较小值，容量由短板决定

【完整代码】

Java

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int ans = 0;
        for (int i = 0; i &lt; n - 1; i++) {
            for (int j = i + 1; j &lt; n; j++) {
                int area = (j - i) * Math.min(height[i], height[j]);
                ans = Math.max(ans, area);
            }
        }
        return ans;
    }
}

【题解】

一句话速通：左右双指针从两端向中间收缩，每次移动较短一侧的指针，沿途更新最大面积，利用短板效应剪枝，一趟扫描得到答案。

【算法思想】

双指针：左右指针相向移动，逐步缩小搜索空间
贪心：每次移动较矮指针，因为较矮侧已经限制了当前宽度的最大容量，保留更高侧才可能获得更大面积

【核心思路】

初始化左指针 l = 0，右指针 r = n-1，答案 ans = 0
当 l < r 时循环：
计算当前面积 area = (r - l) × min(height[l], height[r])
用 ans = max(ans, area) 更新最大值
哪边矮就移动哪边：若 height[l] < height[r] 则 l++，否则 r--
循环结束返回 ans

【复杂度】

时间复杂度 $O(n)$ ：左右指针最多各移动 n 次，总共扫描一遍数组
空间复杂度 $O(1)$ ：只使用指针和临时变量

【伪代码】

text

l = 0, r = n-1, ans = 0
while l &lt; r:
    area = (r - l) * min(height[l], height[r])
    ans = max(ans, area)
    if height[l] &lt; height[r]:
        l = l + 1
    else:
        r = r - 1
return ans

【易错点】

必须移动较矮的指针，若移动较高的那侧，宽度减少但高度不可能超过原来的较矮侧，容量必然更小
宽度是 r - l，不要写成 r - l + 1
当两边高度相等时，移动任意一边均可，可按常规 else 分支处理

【完整代码】

Java

class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int ans = 0;
        while (l &lt; r) {
            int area = (r - l) * Math.min(height[l], height[r]);
            ans = Math.max(ans, area);
            if (height[l] &lt; height[r]) {
                l++;
            } else {
                r--;
            }
        }
        return ans;
    }
}

3 三数之和

【原始题目】

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

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

示例 1：

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

示例 2：

输入：nums = [0,1,1] 输出：[]

示例 3：

输入：nums = [0,0,0] 输出：[[0,0,0]]

提示：

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

【题目速记】

在无序整数数组中，找出所有三个不同位置的元素，使它们的和为 0。需要返回全部不重复的三元组集合，且不能包含重复组合。

【题解】

一句话速通：排序后固定第一个数，转化为两数之和问题，用对撞双指针扫描剩余区间，并通过跳过重复值实现去重。

【算法思想】

排序 + 双指针：将数组排序后，固定最外层元素，内层使用左右指针从两端向中间逼近目标和，利用有序性一次排除多个组合。
去重技巧：在三个维度（外层固定值、左指针值、右指针值）上跳过连续重复元素，避免产生重复三元组。

【核心思路】

将数组 nums 升序排序，方便后续跳过重复值并控制指针移动方向。
遍历数组，以每个 nums[i] 作为三元组中的第一个数。如果 nums[i] > 0，由于数组已排序，后面不可能再凑出和为 0，直接结束循环。
对于当前 i，若与前一个元素相同则跳过，避免固定值重复带来的整体重复。
设置左指针 L = i + 1，右指针 R = n - 1，在区间 (i+1, n-1) 内寻找两数之和等于 -nums[i]。
若三数之和等于 0，收集该三元组，然后同时移动 L 和 R，并跳过重复的 nums[L] 和 nums[R]。
若三数之和小于 0，说明左指针值过小，L++；若大于 0，则右指针值过大，R--。
最后返回收集到的所有三元组列表。

【复杂度】

时间复杂度 $O(n^2)$ ：排序 $O(n \log n)$，外层循环及内层双指针整体遍历每个元素一次，相当于 $O(n^2)$。
空间复杂度 $O(\log n)$ ：排序所引起的栈空间消耗（若忽略输出列表的存储，则为 $O(1)$ 额外空间）。

【伪代码】

text

排序 nums
结果列表 res
for i = 0 到 n-1:
    若 nums[i] > 0 则 break
    若 i>0 且 nums[i]==nums[i-1] 则 continue
    L = i+1, R = n-1
    当 L &lt; R:
        sum = nums[i] + nums[L] + nums[R]
        若 sum == 0:
            添加 [nums[i], nums[L], nums[R]] 到 res
            L++, R--
            跳过重复的 nums[L] 和 nums[R]
        若 sum &lt; 0: L++
        若 sum > 0: R--
返回 res

【易错点】

忘记在外层循环判断 nums[i] > 0 时提前退出，可能浪费时间并引入冗余逻辑。
收集结果后只移动一个指针，或者没有跳过重复元素，导致结果出现重复三元组。
跳过重复元素时，没有检查指针越界（例如 while(L < R && nums[L] == nums[L+1]) 前未保证 L<R）。
先后顺序错误：必须先收集结果，再去重移动指针，否则可能漏掉正确组合。

【完整代码】

Java

class Solution {
    public List&lt;List&lt;Integer>> threeSum(int[] nums) {
        List&lt;List&lt;Integer>> res = new ArrayList&lt;>();
        int n = nums.length;
        if (n &lt; 3) return res;

        Arrays.sort(nums);

        for (int i = 0; i &lt; n - 2; i++) {
            // 最小的数已经大于0，后面的和不可能为0
            if (nums[i] > 0) break;

            // 跳过重复的固定值
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int L = i + 1;
            int R = n - 1;
            while (L &lt; R) {
                int sum = nums[i] + nums[L] + nums[R];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[L], nums[R]));
                    // 移动并跳过重复的左值
                    while (L &lt; R && nums[L] == nums[L + 1]) L++;
                    // 移动并跳过重复的右值
                    while (L &lt; R && nums[R] == nums[R - 1]) R--;
                    L++;
                    R--;
                } else if (sum &lt; 0) {
                    L++;
                } else {
                    R--;
                }
            }
        }
        return res;
    }
}

4 接雨水

【原始题目】

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

示例 1：输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6

示例 2：输入：height = [4,2,0,3,2,5] 输出：9

【题目速记】

数组表示柱子高度，宽度均为 1。雨水只能积在凹槽中，求总共能接的雨水单位数。核心是每个位置能积的水量由它左右两侧最高的柱子中的较小者决定。

【题解】

一句话速通：用两个数组预处理每个位置左边和右边的最大高度，然后对每个位置累加 min(左max, 右max) - height[i]，即为总雨水量。

【算法思想】

动态规划/预处理：提前算出每个下标左侧的最高柱子和右侧的最高柱子，避免重复扫描。
前缀最值数组：leftMax[i] 表示 [0, i] 区间内的最大值，rightMax[i] 表示 [i, n-1] 区间内的最大值。
按列求水：每一列能接的雨水 = 左右最高中的短板 - 当前柱子高度，若为负则取 0。

【核心思路】

创建 leftMax 数组，从左到右填充：leftMax[i] = max(leftMax[i-1], height[i])。
创建 rightMax 数组，从右到左填充：rightMax[i] = max(rightMax[i+1], height[i])。
遍历每个位置 i，计算积水量 min(leftMax[i], rightMax[i]) - height[i]，累加到结果。

【复杂度】

时间复杂度 $O(n)$ ：三次线性遍历。
空间复杂度 $O(n)$ ：两个辅助数组 leftMax 和 rightMax。

【伪代码】

text

n = height.length
leftMax[0] = height[0]
for i from 1 to n-1:
    leftMax[i] = max(leftMax[i-1], height[i])

rightMax[n-1] = height[n-1]
for i from n-2 down to 0:
    rightMax[i] = max(rightMax[i+1], height[i])

ans = 0
for i from 0 to n-1:
    ans += min(leftMax[i], rightMax[i]) - height[i]
return ans

【易错点】

leftMax 和 rightMax 的初始化边界，leftMax[0] 和 rightMax[n-1] 容易写成 0。
计算积水量时若当前柱子高于左右短板，减法得负数，但 min(leftMax, rightMax) 至少等于当前高度，所以不会为负。但如果忘记取 min 直接用一侧最大值会多算。

【完整代码】

Java

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) return 0;

        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        for (int i = 1; i &lt; n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i &lt; n; i++) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

【题解】

一句话速通：用双指针从两端向中间收缩，动态维护左右最大高度，每次由较小高度的一边计算水量并向内移动，用常数空间完成。

【算法思想】

双指针：left 和 right 分别从数组两端向中间移动。
动态维护最值：leftMax 记录 [0, left] 的最大高度，rightMax 记录 [right, n-1] 的最大高度。
蓄水原理：对于当前 left 位置，如果 leftMax < rightMax，则 left 处的积水量由 leftMax 决定，因为右侧至少有一个 rightMax 保底，可安全计算并右移 left；否则处理 right 位置。

【核心思路】

初始化 left = 0, right = n-1, leftMax = 0, rightMax = 0, ans = 0。
当 left < right 时循环：
- 如果 height[left] < height[right]：
  - 更新 leftMax = max(leftMax, height[left])
  - ans += leftMax - height[left]
  - left++
- 否则：
  - 更新 rightMax = max(rightMax, height[right])
  - ans += rightMax - height[right]
  - right--
返回 ans。

【复杂度】

时间复杂度 $O(n)$ ：两个指针对撞，每个元素访问一次。
空间复杂度 $O(1)$ ：只用了几个变量。

【伪代码】

text

left = 0, right = n-1
leftMax = 0, rightMax = 0, ans = 0
while left &lt; right:
    if height[left] &lt; height[right]:
        leftMax = max(leftMax, height[left])
        ans += leftMax - height[left]
        left++
    else:
        rightMax = max(rightMax, height[right])
        ans += rightMax - height[right]
        right--
return ans

【易错点】

判断条件写成 leftMax < rightMax 而不是 height[left] < height[right]。必须比较当前柱子高度才能确保每次只移动一边，且内侧有足够高的屏障。
更新 leftMax 或 rightMax 后再计算差值，若先计算差值可能出错（因为当前柱子可能更新最大值）。
循环条件 left < right，当指针相遇时退出，相遇点不需要计算，因为这是最高点或已经被覆盖。

【完整代码】

Java

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int ans = 0;

        while (left &lt; right) {
            if (height[left] &lt; height[right]) {
                leftMax = Math.max(leftMax, height[left]);
                ans += leftMax - height[left];
                left++;
            } else {
                rightMax = Math.max(rightMax, height[right]);
                ans += rightMax - height[right];
                right--;
            }
        }
        return ans;
    }
}

【题解】

一句话速通：用单调递减栈存储柱子下标，遇到更高的柱子时弹出栈顶并计算低洼层积水量，宽度由当前柱子与新的栈顶的距离决定。

【算法思想】

单调栈：栈中存放数组下标，保持高度严格递减。当遇到一个比栈顶高的柱子时，说明找到了一个凹槽的右边界。
分层计算：每弹出一个栈顶元素，计算以它为底的积水层，高度为 min(当前柱子, 新栈顶柱子) - 弹出柱子高度，宽度为 当前下标 - 新栈顶下标 - 1。
横向分层累加：不是按列计算，而是按行一层层地把凹槽填满。

【核心思路】

初始化栈，遍历数组 i 从 0 到 n-1。
当栈非空且 height[i] > height[stack.peek()]：
- 弹出栈顶 top。
- 若栈为空，说明左边没有围墙，无法积水，跳出。
- 距离 dist = i - stack.peek() - 1。
- 积水高度 boundedH = min(height[i], height[stack.peek()]) - height[top]。
- ans += dist * boundedH。
将当前下标 i 入栈。
返回 ans。

【复杂度】

时间复杂度 $O(n)$ ：每个元素最多入栈出栈一次。
空间复杂度 $O(n)$ ：栈在最坏情况下存储所有下标。

【伪代码】

text

stack = empty stack
ans = 0
for i from 0 to n-1:
    while stack not empty and height[i] > height[stack.top()]:
        top = stack.pop()
        if stack empty: break
        dist = i - stack.top() - 1
        boundedH = min(height[i], height[stack.top()]) - height[top]
        ans += dist * boundedH
    stack.push(i)
return ans

【易错点】

弹出栈顶后一定要检查栈是否为空，为空则无法形成凹槽，直接跳出。
计算距离时要减一：i - stack.peek() - 1，因为积水区间是开区间，不含左右边界。
注意栈中存的是下标，计算高度时要取值。

【完整代码】

Java

class Solution {
    public int trap(int[] height) {
        Deque&lt;Integer> stack = new ArrayDeque&lt;>();
        int ans = 0;
        for (int i = 0; i &lt; height.length; i++) {
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int top = stack.pop();
                if (stack.isEmpty()) break;
                int dist = i - stack.peek() - 1;
                int boundedH = Math.min(height[i], height[stack.peek()]) - height[top];
                ans += dist * boundedH;
            }
            stack.push(i);
        }
        return ans;
    }
}

双指针 ​

1 移动零 ​

【原始题目】 ​

【题目速记】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

2 盛最多水的容器 ​

【原始题目】 ​

【题目速记】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

3 三数之和 ​

【原始题目】 ​

【题目速记】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

4 接雨水 ​

【原始题目】 ​

【题目速记】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

【题解】 ​

【算法思想】 ​

【核心思路】 ​

【复杂度】 ​

【伪代码】 ​

【易错点】 ​

【完整代码】 ​

双指针

1 移动零

【原始题目】

【题目速记】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】

2 盛最多水的容器

【原始题目】

【题目速记】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】

3 三数之和

【原始题目】

【题目速记】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】

4 接雨水

【原始题目】

【题目速记】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】

【题解】

【算法思想】

【核心思路】

【复杂度】

【伪代码】

【易错点】

【完整代码】