hot100双指针题解
283. 移动零
问题描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
1
2
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
1
2
输入: nums = [0]
输出: [0]
提示:
- $1 <= nums.length <= 10^4$
- $-2^{31} <= nums[i] <= 2^{31} - 1$
进阶：你能尽量减少完成的操作次数吗？
题解
以下是 移动零 的 C++ 解法，采用双指针方法来实现高效的原地操作。
解题思路
- 双指针方法：
- 使用两个指针，一个
slow指针用于记录非零元素的插入位置，另一个fast指针用于遍历数组。 - 当
fast指向非零元素时，将其移动到slow指针的位置，然后移动slow指针。
- 使用两个指针，一个
- 补零：
- 遍历完成后，从
slow指针开始，将剩余位置填充为零。
- 遍历完成后，从
C++ 代码实现
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
33
34
#include <iostream>
#include <vector>
using namespace std;
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;
}
}
// 将剩余的位置填充为0
for (int i = slow; i < nums.size(); ++i) {
nums[i] = 0;
}
}
int main() {
vector<int> nums = {0, 1, 0, 3, 12};
moveZeroes(nums);
// 输出结果
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
代码解析
- 双指针遍历：
fast指针用于遍历整个数组。slow指针仅在nums[fast]为非零时向前移动，并将当前值覆盖到slow的位置。
- 填充零：
- 在所有非零元素移动完成后，从
slow开始到数组末尾的位置，统一填充为零。
- 在所有非零元素移动完成后，从
时间复杂度
- 遍历数组：
- 遍历数组一次将非零元素移动到前面，时间复杂度为 $O(n)$。
- 第二次遍历填充零，时间复杂度也是 $O(n)$。
- 整体时间复杂度：
- $O(n)$。
空间复杂度
- 使用了固定的指针变量，没有额外的空间开销。
- 空间复杂度为 $O(1)$。
示例运行
输入：
1
nums = [0, 1, 0, 3, 12]
输出：
1
[1, 3, 12, 0, 0]
进阶优化
- 双指针方法已经是线性时间复杂度，并且没有使用额外的空间，符合题目要求的高效解法。
11. 盛最多水的容器
问题描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
1
2
3
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
1
2
输入：height = [1,1]
输出：1
提示：
n == height.length- $2 <= n <= 10^5$
- $0 <= height[i] <= 10^4$
题解
以下是 盛最多水的容器 的 C++ 解法，采用双指针法实现 O(n)O(n) 的时间复杂度。
解题思路
- 双指针法：
- 使用两个指针，
left指向数组的起始位置，right指向数组的末尾位置。 - 计算当前两个指针构成容器的容量：
area = min(height[left], height[right]) * (right - left)。 - 移动指针：
- 总是移动较小值对应的指针，因为容器的高度由较短的那一边决定。
- 移动后可能找到更大的容量。
- 使用两个指针，
- 终止条件：
- 当
left和right指针重合时，结束遍历。
- 当
C++ 代码实现
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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1; // 初始化双指针
int maxArea = 0; // 用于记录最大面积
while (left < right) {
// 计算当前的面积
int currentArea = min(height[left], height[right]) * (right - left);
maxArea = max(maxArea, currentArea); // 更新最大面积
// 移动指针，选择较短的一边
if (height[left] < height[right]) {
++left;
} else {
--right;
}
}
return maxArea;
}
int main() {
vector<int> height = {1, 8, 6, 2, 5, 4, 8, 3, 7};
cout << "Max Area: " << maxArea(height) << endl;
return 0;
}
代码解析
- 双指针遍历：
- 指针
left和right分别从数组的两端开始向中间移动。 - 每次计算以当前两个指针为边界的容器容量。
- 指针
- 更新最大值：
- 使用
maxArea = max(maxArea, currentArea)更新最大容器容量。
- 使用
- 移动指针：
- 移动较短的一边，因为只有增加高度才有可能增加容量。
时间复杂度
- 双指针遍历：
- 每次移动一个指针，总共最多遍历 $n$ 次。
- 时间复杂度为 $O(n)$。
空间复杂度
- 只使用了固定的变量，空间复杂度为 $O(1)$。
示例运行
输入：
1
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
输出：
1
49
解释：
在索引 1 和索引 8 处的两条线构成的容器，能够盛水的最大容量为 min(8,7)×(8−1)=49\min(8, 7) \times (8 - 1) = 49。
总结
- 双指针法 是解决此类问题的高效方法，具有线性时间复杂度。
- 此方法通过每次移动较短边来优化搜索空间，并保持正确性。
15. 三数之和
问题描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
1
2
3
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
1
2
3
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000- $-10^5 <= nums[i] <= 10^5$
题解
以下是 三数之和 的 C++ 解法，利用排序和双指针方法解决，时间复杂度为 O(n2)O(n^2)。
解题思路
- 排序：
- 首先将数组排序，以便后续使用双指针查找和为 0 的组合。
- 固定一个数，双指针寻找：
- 遍历数组，固定一个数
nums[i]。 - 使用双指针在排序后的数组中寻找两个数，使它们的和等于
-nums[i]。 - 左指针
left从当前元素之后开始，右指针right从数组末尾开始。
- 遍历数组，固定一个数
- 避免重复：
- 跳过重复的数字，确保每个三元组唯一。
- 调整指针：
- 如果当前三数之和小于 0，移动左指针。
- 如果大于 0，移动右指针。
- 如果等于 0，记录结果，并调整指针以跳过重复值。
C++ 代码实现
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end()); // 排序数组
for (int i = 0; i < nums.size(); ++i) {
// 跳过重复的数字
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
++left; // 总和小于0，左指针右移
} else if (sum > 0) {
--right; // 总和大于0，右指针左移
} 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;
}
int main() {
vector<int> nums = {-1, 0, 1, 2, -1, -4};
vector<vector<int>> result = threeSum(nums);
// 输出结果
for (const auto& triplet : result) {
cout << "[";
for (int num : triplet) {
cout << num << " ";
}
cout << "]" << endl;
}
return 0;
}
代码解析
- 排序：
- 排序后的数组可以通过双指针高效查找，确保结果有序且便于去重。
- 双指针查找：
- 每次固定一个数，剩下的问题变成两数之和，使用双指针解决。
- 去重：
- 遍历时，跳过当前元素及指针位置的重复值，避免重复的三元组。
- 指针移动：
- 当找到一个三元组后，继续移动指针以查找新的组合。
时间复杂度
- 排序：
- 时间复杂度为 $O(n \log n)$。
- 双指针：
- 外层遍历 $n$ 次，内层查找最多遍历 $n$ 次，因此双指针部分复杂度为 $O(n^2)$。
- 总复杂度：
- $O(n^2)$。
空间复杂度
- 排序使用的空间复杂度为 $O(\log n)$，其余为常数级额外空间。
- 总空间复杂度为 $O(\log n)$。
示例运行
输入：
1
nums = [-1, 0, 1, 2, -1, -4]
输出：
1
2
[-1, -1, 2]
[-1, 0, 1]
总结
- 该方法通过排序和双指针高效解决了三数之和问题。
- 去重逻辑保证了结果的唯一性。
42. 接雨水
问题描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
1
2
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length- $1 <= n <= 2 * 10^4$
- $0 <= height[i] <= 10^5$
题解
以下是 接雨水 的 C++ 解法，采用双指针方法，时间复杂度为 O(n)O(n)。
解题思路
- 问题核心：
- 雨水能够被接住的条件是当前柱子两侧存在更高的柱子，雨水量等于当前柱子高度和两侧柱子高度的最小值之间的差值。
- 双指针法：
- 使用两个指针
left和right，分别从数组两端向中间移动。 - 使用两个变量
leftMax和rightMax，记录当前左侧和右侧的最高柱子高度。 - 根据
leftMax和rightMax的较小值决定哪侧可以确定雨水量：- 如果
leftMax < rightMax，移动left指针并更新leftMax。 - 如果
rightMax <= leftMax，移动right指针并更新rightMax。
- 如果
- 使用两个指针
- 计算雨水量：
- 对于每个柱子，雨水量为
min(leftMax, rightMax) - height[i]。
- 对于每个柱子，雨水量为
C++ 代码实现
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
33
34
35
36
37
38
39
#include <iostream>
#include <vector>
using namespace std;
int trap(vector<int>& height) {
int left = 0, right = height.size() - 1;
int leftMax = 0, rightMax = 0;
int totalWater = 0;
while (left < right) {
if (height[left] < height[right]) {
// 更新左侧最高柱子高度
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
totalWater += leftMax - height[left];
}
++left; // 移动左指针
} else {
// 更新右侧最高柱子高度
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
totalWater += rightMax - height[right];
}
--right; // 移动右指针
}
}
return totalWater;
}
int main() {
vector<int> height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
cout << "Trapped Rainwater: " << trap(height) << endl;
return 0;
}
代码解析
- 初始化指针和变量：
left和right指向数组两端。leftMax和rightMax记录当前左侧和右侧的最高柱子高度。
- 双指针移动：
- 比较
height[left]和height[right]：- 若
height[left] < height[right]，可以确定左侧的雨水量，因为左侧的最大高度leftMax不可能被右侧的柱子改变。
- 若
- 比较
- 累积雨水量：
- 每次移动指针时，更新对应的最大高度，并累积当前柱子的雨水量。
时间复杂度
- 遍历数组：
- 每个指针最多遍历整个数组一次，时间复杂度为 $O(n)$。
- 总复杂度：
- $O(n)$。
空间复杂度
- 使用了固定数量的变量，空间复杂度为 $O(1)$。
示例运行
输入：
1
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
输出：
1
6
解释：
- 图中蓝色部分为能够接住的雨水，总量为 6。
总结
- 双指针法是一种高效解决接雨水问题的方法，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。
- 通过动态更新
leftMax和rightMax，确保计算的雨水量始终正确。
本文由作者按照 CC BY 4.0 进行授权