三数之和
题目描述
给你一个整数数组 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]] 解释： 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：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0。
- 示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0。
思路分析
我们首先来看题目的要求，题目要求我们在当前的数组里面找到三个数字之和等于 0 的三个元素，那么我们可以先将这个数组进行排序，然后固定一个位置的元素，然后去遍历剩下位置的元素，去找到两个元素之和等于 -nums[n]，由此我们就把三数和问题变成了两数和问题。
那么对于两数和的问题，同时这个数组已经有序了，我们可以使用双指针的思路，定义两个指针 left 和 right，然后进行对撞遍历，去看两个指针指向的元素之和是否等于 -nums[n]，如果等于，那么就把 n，left 和 right 位置的元素插入到目标数组里面；如果两个元素之和小于 -nums[n]，那么就让 left 指针向前走，因为数组是有序的；如果两个元素之和大于 -nums[n]，那么就让 right 指针向后走；但是这里我们还有一个问题，就是如何去重，如果我们找到了等于 -nums[n] 的两个元素，我们这两个指针还要继续进行对撞遍历，并进行去重的操作，目的是为了将这个区间内的所有符合要求的元素都找出来。
接下来我们就来讨论第三个元素，我们发现，如果我们只进行一次操作，无法找到所有满足要求的元素，所以我们需要进行循环遍历，也就是说，我们需要定义一个循环，让这个 n 走完整个数组。
根据上面的分析，我们可以写下如下代码。
代码编写
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size() - 1;
vector<vector<int>> result;
while (n >= 2) {
if (nums[n] < 0) {
break;
}
int left = 0, right = n - 1;
int target = -nums[n];
while (left < right) {
if (nums[left] + nums[right] > target) {
--right;
} else if (nums[left] + nums[right] < target) {
++left;
} else {
result.push_back({nums[n], nums[left], nums[right]});
++left;
while (left < right && nums[left] == nums[left - 1]) {
++left;
}
--right;
while (left < right && nums[right] == nums[right + 1]) {
--right;
}
}
}
--n;
while (n >= 0 && nums[n] == nums[n + 1]) {
--n;
}
}
return result;
}
};
盛水最多的容器
题目描述
给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
- 示例 1：
输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
- 示例 2：
输入：height = [1,1] 输出：1
思路分析
题目要求我们找出盛水最多的容器，我们来看一下这个盛水量是如何进行计算的，假设我们的盛水量是 volume，左边界的指针为 left，右边界的指针是 right，那么它的计算公式是：
volume=min(height[left],height[right])*(right-left)
通过观察我们发现上面的公式，我们发现，如果我们想要让盛水量最大，那么 min(height[left],height[right]) 和 right-left 也应该最大，为了让 right-left 最大，我们可以让 left 从最左边开始，right 从最右边开始，然后两个指针对撞遍历，此时 right-left 的大小是逐渐递减的，所以我们需要让 min(height[left],height[right]) 最大，所以我们需要对比 height[left] 和 height[right] 的值，保留较大的那一部分，然后移动较小的部分，直到两个指针相遇，根据我们的思路，我们可以写下如下代码。
代码编写
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0, right = height.size() - 1;
int maxSize = 0;
while (left < right) {
int volume;
if (height[left] < height[right]) {
volume = height[left] * (right - left);
++left;
} else {
volume = height[right] * (right - left);
--right;
}
maxSize = max(volume, maxSize);
}
return maxSize;
}
};
移动零
题目描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意，必须在不复制数组的情况下原地对数组进行操作。
- 示例 1：
输入：nums = [0,1,0,3,12] 输出：[1,3,12,0,0]
- 示例 2：
输入：nums = [0] 输出：[0]
思路分析
这道题的思路依然是双指针的思路，我们可以定义两个指针，一个指针去遍历整个数组找到不为 0 的元素，另一个指针去寻找为 0 的元素，然后进行交换即可，交换完毕指针继续向前走，直到走到数组末尾。
由此我们可以写下如下代码。
代码编写
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int left = 0, right = 0;
while (left <= right && right < nums.size()) {
if (nums[right]) {
swap(nums[left++], nums[right++]);
} else {
++right;
}
}
}
};
