leetcode-hot-100(双指针)

1. 移动零

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

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

解答

类似于签到题，比较容易。

class Solution {
public:void moveZeroes(vector<int>& nums) {for (int i = 0, j = 0; i < nums.size(); ++i) {if (nums[i] != 0) {swap(nums[i], nums[j]);j++;}}}
};

上述代码和官方的差不多，官方如下：

class Solution {
public:void moveZeroes(vector<int>& nums) {int len = nums.size(), left = 0, right = 0;while (right < len) {if (nums[right]) {swap(nums[left], nums[right]);left++;}right++;}}
};

主要就是需要看右边是啥样的，也就是说，要是右指针指向的位置不为零，则交换左右指针。我一开始编写的代码如下，查看的是左指针，于是出现了很多错误：

class Solution {
public:void moveZeroes(vector<int>& nums) {int len = nums.size(), left = 0, right = 1;while (right < len) {// 问题 1: 这里只跳过右边是 0 的情况，没有意义。// 它只是让 right 跳过连续的 0，但 left 依然可能是 0。while (right < len && nums[right] == 0)right++;// 问题 2: 如果 nums[left] 不是 0，就不交换，但是 left 永远不会越过这个位置，// 导致后面即使有非零数字也无法向前移动。if (nums[left] == 0 && right < len) {swap(nums[left], nums[right]);}left++;right++;}}
};

要是实在是想这样写的话，GPT给的答案不错：

class Solution {
public:void moveZeroes(vector<int>& nums) {int len = nums.size(), left = 0, right = 1;// 确保 right 不会越界while (right < len && left < len) {// 移动 left 直到找到一个 0while (left < len && nums[left] != 0) {left++;// 确保 right 始终在 left 右边或与之相同if (right < left) right = left + 1;}// 如果 left 已经到达数组末尾，退出循环if (left >= len) break;// 移动 right 直到找到一个非 0 元素while (right < len && nums[right] == 0) {right++;}// 如果 right 到达数组末尾，退出循环if (right >= len) break;// 交换 left 和 right 所指的元素swap(nums[left], nums[right]);// 交换后移动 left 和 right 指针left++;right++;}}
};

2. 盛最多水的容器

题目链接：盛最多水的容器
题目描述：给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

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

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

说明：你不能倾斜容器。

解答

我觉得这个大佬写的不错，放在这里供大家欣赏，这道题目主要是需要弄懂为啥使用双指针是正确的，以及为啥设置双指针可以全部遍历所有的情况。
大佬解答

要是思想弄懂，代码其实都是差不多的：

class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1;int ans = 0;while (left < right) {int temp = min(height[left], height[right]) * (right - left);ans = max(ans, temp);if (height[left] >= height[right])right--;elseleft++;}return ans;
};

解答那位大佬的博客写的不错，我这里就不详细的论述了，下面主要讨论两个问题。
1.为啥使用双指针是对的？
2.上面的解法（两端指针向中间移动）不会遗漏情况吗？
下面就这两个问题简要说明一下。
说实话，一开始我的想法是：使用两个指针，两个for，从前向后一直遍历，直到找到最优解，代码如下：

class Solution {
public:int maxArea(vector<int>& height) {int len = height.size();int ans = 0;for (int left = 0; left < len; left++) {for (int right = left + 1; right < len; right++) {int temp = min(height[left], height[right]) * (right - left);ans = max(ans, temp);}}return ans;}
};

但是很不幸的是，这段代码超出了时间限制。

因此上述这样使用双指针的话，就不对。因为两个for的时间复杂度实在是太高了。那么可不可以将时间复杂度降低呢？排序肯定没法用，于是只能想到还是使用两个双指针，但是这次一个左指针在开始位置，一个右指针在结尾的位置，然后一次向中间移动。这样的话，底层是贪心的思想，永远找最高的和最远的，局部最优推出全局最优。上述解法肯定存在遗漏（不然就更for嵌套一样慢了）但是遗漏的都是非局部最优解，所以对全局最优解没有影响。

3. 三数之和

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

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

解答

好，看到此题的第一想法，就是上循环，毕竟用 for 是真的香。也就是上三重循环，遍历整个数组，然后得到满足条件的数组，当然，由于题目要求不含有重复的三元组，因此还需要使用哈希表进行去重，于是代码编写如下：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n = nums.size();vector<vector<int>> ans;unordered_set<string> seen;for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {for (int k = j + 1; k < n; ++k) {if (nums[i] + nums[j] + nums[k] == 0) {// 去重：先排序再转成字符串判断是否重复vector<int> triplet = {nums[i], nums[j], nums[k]};sort(triplet.begin(), triplet.end());string key = to_string(triplet[0]) + "," + to_string(triplet[1]) + "," + to_string(triplet[2]);                        if (seen.find(key) == seen.end()) {ans.push_back(triplet);seen.insert(key);}}}}}return ans;}
};

过测试用例没有问题，然后提交，发现：

其实这也好理解，如果我们直接使用三重循环枚举三元组，会得到 $O(N^3)$ 个满足题目要求的三元组（其中 $N$ 是数组的长度）时间复杂度至少为 $O(N^3)$。在这之后，我们还需要使用哈希表进行去重操作，得到不包含重复三元组的最终答案，又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高,肯定是有些测试用例过不了的。

上述代码不行的话，就需要另想方法了。
既然题目需要不重复，那么就只需要保证如下的性质即可：

• 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
• 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。

也就是说，我们枚举的三元组 $(a,b,c)$ 满足 $a\le b\le c$，保证了只有 $(a,b,c)$ 这个顺序会被枚举到，而 $(b,a,c)$、$(c,b,a)$ 等等这些不会，这样就减少了重复。要实现这一点，我们可以将数组中的元素从小到大进行排序，随后使用普通的三重循环就可以满足上面的要求。
代码如下：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ans;int n = nums.size();        // 排序以便去重sort(nums.begin(), nums.end());        for (int first = 0; first < n; ++first) {// 跳过重复的 firstif (first > 0 && nums[first] == nums[first - 1]) continue;            for (int second = first + 1; second < n; ++second) {// 跳过重复的 secondif (second > first + 1 && nums[second] == nums[second - 1]) continue;                for (int third = second + 1; third < n; ++third) {// 跳过重复的 thirdif (third > second + 1 && nums[third] == nums[third - 1]) continue;                    // 判断三数之和是否为 0if (nums[first] + nums[second] + nums[third] == 0) {ans.push_back({nums[first], nums[second], nums[third]});}}}}        return ans;}
};

但是时间复杂度还是 $O(N^3)$，因此还是可以继续进行优化的，因为上述循环还是没有改变三个 for 的情况。于是还需要继续进行优化：
可以发现，如果我们固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a + b + c = 0。当第二重循环往后枚举一个元素 b' 时，由于 b' > b，那么满足 a + b' + c' = 0 的 c' 一定有 c' < c，即 c' 在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c，即第二重循环和第三重循环实际上是并列的关系。

由于之前将数组进行了排序，因此就可以保持第二重循环不变，而将第三重循环变成一个从数组最右端开始向左移动的指针。
官方给出的伪代码如下：

nums.sort()
for first = 0 .. n-1if first == 0 or nums[first] != nums[first-1] then// 第三重循环对应的指针third = n-1for second = first+1 .. n-1if second == first+1 or nums[second] != nums[second-1] then// 向左移动指针，直到 a+b+c 不大于 0while nums[first]+nums[second]+nums[third] > 0third = third-1// 判断是否有 a+b+c==0check(first, second, third)

基于上述思想和伪代码可以编写正确代码如下：

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ans;int n = nums.size();        // 排序数组，便于去重和双指针操作sort(nums.begin(), nums.end());        for (int first = 0; first < n; ++first) {// 跳过重复的 first 元素if (first > 0 && nums[first] == nums[first - 1]) continue;            // third 初始化为最右边的元素int third = n - 1;            for (int second = first + 1; second < n; ++second) {// 跳过重复的 second 元素if (second > first + 1 && nums[second] == nums[second - 1]) continue;                // 将 third 指针向左移动到合适的位置while (second < third && nums[first] + nums[second] + nums[third] > 0) {--third;}                // 检查是否找到满足条件的三元组if (second < third && nums[first] + nums[second] + nums[third] == 0) {ans.push_back({nums[first], nums[second], nums[third]});}}}        return ans;}
};

还是需要多做多看，才能顿悟啊！！！

4. 接雨水

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

解答

方法一：单调栈

使用一个单调栈来记录柱子的索引，栈中元素保持递减顺序。当遇到一个比栈顶高的柱子时，说明可以形成凹槽接雨水。此时弹出栈顶元素，计算其能接的雨水量。
关键点：

• 栈保存的是索引。
• 每次计算的是中间凹陷部分的高度差和宽度。
• 只有在左右两边都有更高柱子的情况下才能接到水。

class Solution {
public:int trap(vector<int>& height) {int n = height.size();stack<int> stk;  // 存储索引int ans = 0;for (int i = 0; i < n; ++i) {while (!stk.empty() && height[i] > height[stk.top()]) {int top = stk.top();  // 当前要计算的底部位置stk.pop();if (stk.empty()) break;  // 没有左边的墙，无法接水int distance = i - stk.top() - 1; // 这里不能使用 int distance = i - top; // 因为top和stk.top()不一定相邻。int bounded_height = min(height[i], height[stk.top()]) - height[top];ans += distance * bounded_height;}stk.push(i);}return ans;}
};

上述结果提交发现前面还有很多人的算法的时间复杂度和空间复杂度都比上述算法的好，因此说明上述代码还是可以继续进行优化的。
这里的部分贴上的标签就是双指针，那么是否可以使用双指针进行求解呢。

方法二：双指针

双指针的大致思想如下：

维护两个指针 left 和 right，分别从左右两端向中间移动。同时，我们也会维护两个变量 leftMax 和 rightMax，分别表示当前左侧和右侧的最大高度。
以某个位置（例如图中的值为 1 的位置）为例：此时左边的最大高度是 1，右边的最大高度是 3。根据木桶原理，能接到的雨水量取决于左右两边最大值中较小的那个。
也就是说，该位置能接的雨水量等于 min(leftMax, rightMax) - height[i]。
因此，只要 leftMax < rightMax，我们就可以确定当前位置的储水量由 leftMax 决定，无需等到完全遍历整个数组。同理，如果 rightMax <= leftMax，则由 rightMax 决定。
这种方法的核心思想是：通过双指针动态判断当前哪一侧的高度受限于局部最大值，从而逐步计算出每个位置的储水量。

一句话：就是分析某一个位置的雨水量，就看其左边（包含自己）最大和右边最大的两者的最小值是谁，然后减去自己位置的高度，最优对每一个位置累加即可。

class Solution {
public:int trap(vector<int>& height) {int ans = 0;int left = 0, right = height.size() - 1;int leftMax = 0, rightMax = 0;while (left < right) {leftMax = max(leftMax, height[left]);rightMax = max(rightMax, height[right]);if (height[left] < height[right]) {ans += leftMax - height[left];++left;} else {ans += rightMax - height[right];--right;}}return ans;}
};

评论区还有一些我觉得不错的答案，复制过来分析一下。

FIRST：

试想被水填满后的情况，最高柱子左侧水位必然是递增的，右侧水位必然是递减的，不可能出现中间有凹的情况（凹会被水填满）。于是只要找到最高柱子的位置，左侧一次正向遍历，右侧一次反向遍历，即可实时计算水位并累计水位高度差作为积水量。

class Solution {
public:int trap(vector<int>& height) {int maxHeight = 0;int maxHeightPos = -1;for (int i=0;i<height.size();i++) {if (height[i] > maxHeight) {maxHeight = height[i];maxHeightPos = i;}}if (maxHeightPos == -1) return 0;int waterHeight = 0;int waterSum = 0;for (int i=0;i<maxHeightPos;i++) {// 左侧水位if (height[i] > waterHeight) waterHeight = height[i];waterSum += waterHeight - height[i];}waterHeight = 0;for (int i=height.size()-1;i>maxHeightPos;i--) {// 右侧水位if (height[i] > waterHeight) waterHeight = height[i];waterSum += waterHeight - height[i];}return waterSum;}
};

SECOND：

按行求，按列求