移动零

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

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

必须原地操作，不能额外开数组。用一个慢指针 slow 记录下一个非零元素应该放的位置，快指针 fast 遍历数组，将非零元素直接覆盖到 slow 处，最后把 slow 之后的位置全部置零。这样每个元素最多被写一次，且保持相对顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int slow = 0;
        for (int fast = 0; fast < nums.size(); ++fast) {
            if (nums[fast] != 0) {
                nums[slow] = nums[fast];
                ++slow;
            }
        }
        while (slow < nums.size()) {
            nums[slow] = 0;
            ++slow;
        }
    }
};

盛水最多的容器

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

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

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

说明：你不能倾斜容器。

感觉之前在 B 站上被推到不止一次了🫪。

用左右指针 left 和 right 分别指向数组两端。每次计算当前容器的水量 min(height[left], height[right]) * (right - left) 并更新最大值。然后移动较矮的那个指针（因为移动较高的指针不会使水量增加，而移动较矮的指针才有可能找到更大的水量）。重复以上步骤直到两指针相遇。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxArea(vector<int>& height) {
        int max_water = 0;
        int left = 0;
        int right = height.size() - 1;

        while (left < right) {
            int w = right - left;
            if (height[left] < height[right]) {
                max_water = max(height[left] * w, max_water);
                left++;
            } else {
                max_water = max(height[right] * w, max_water);
                right--;
            }
        }

        return max_water;
    }
};

三数之和

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

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

似乎只能列举，再做一些剪枝：

  1. 对数组排序，使相同元素相邻，便于去重。
  2. 遍历排序后的数组，固定第一个数 nums[i]。
    • 若 nums[i] > 0，则后面不可能凑出和为 0，直接结束。
    • 跳过重复的 nums[i] 避免重复解。
  3. 在 i 右侧区间使用双指针 left = i+1、right = n-1：
    • 计算三数之和 sum。
    • 若 sum < 0，左指针右移；若 sum > 0，右指针左移。
    • 若 sum == 0，记录该三元组，并跳过重复的 nums[left] 和 nums[right]，之后同时收缩两指针。
  4. 直到 i 遍历完所有可能的第一个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        int n = nums.size();
        if (n < 3) return result;

        sort(nums.begin(), nums.end());

        for (int i = 0; i < n - 2; ++i) {
            if (nums[i] > 0) break;
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    ++left;
                } else if (sum > 0) {
                    --right;
                } else {
                    result.push_back({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;
                }
            }
        }
        return result;
    }
};

接雨水

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

仍然神秘接水题，这个也被 B 站推过好多次，但是看着麻烦，没一次点进去完整看完过🤡。

视频对该题目的评价：面试毒瘤，某大厂特别爱问。

初始的思路是：对每一个位置，它能接水的量，等于它左侧所有柱子中的最大值和右侧所有柱子中的最大值中的最小值，即 min(leftMax, rightMax)，但是全部扫一遍时间复杂度是 O(n2)O(n^2)，这明显是不行的。

那干脆向右扫一遍，找到对每一个位置及其左边的最大值；再向左扫一遍，找到每一个位置及其右边的最大值。再从左到右遍历一遍，用两个数组中的小值减去当前柱子的高度，就是这个位置的蓄水量。最终复杂度为 O(N)O(N)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        if (n == 0) return 0;

        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

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

        int water = 0;
        for (int i = 0; i < n; ++i) {
            int ceiling = min(leftMax[i], rightMax[i]);
            water += ceiling - height[i];
        }
        return water;
    }
};

但是刚才那个解法没用双指针。AI 给了一个 O(1)O(1)空间的双指针实现：由两端向内收缩，始终处理较矮的那一侧，因为该位置的积水量此时只由该侧的历史最大值决定（另一侧当前高度更高，兜底能力足够），无需预知全局最大值，从而在一次遍历中用 O(1)O(1) 额外空间完成计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() - 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;
    }
};