引言
我们已经在这篇博客【算法/学习】双指针-CSDN博客里面讲了双指针、二分等的相关知识。
现在我们来做一些训练吧
经典例题
1. 移动零
思路：
使用 0 当做这个中间点，把不等于 0(注意题目没说不能有负数)的放到中间点的左边，等于 0 的放到其右边。
这的中间点就是 0 本身，所以实现起来比快速排序简单很多，然后使用双指针 i 和 j，只要 nums[i]!=0，我们就交换 nums[i] 和 nums[j]
class Solution {
public:
void moveZeroes(vector<int>& nums) {
if (nums.size() == 0) return;
// 双指针，前后交换即可
int j = 0;
for (int i = 0; i < nums.size(); i++) {
//当前元素!=0，就把其交换到左边，等于0的交换到右边
if (nums[i] != 0) {
swap(nums[i], nums[j++]);
}
}
}
};2. 复写零
思路：
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
// 1. 找到最后一个复写数
int cur = 0, dest = -1, n = arr.size();
while (cur < n)
{
if (arr[cur]) dest++;
else dest += 2;
if (dest >= n - 1) break;
cur++;
}
// 2. 处理边界清空
if (dest == n)
{
arr[n - 1] = 0;
cur--, dest -= 2;
}
// 3. 从后往前完成复写操作
while (cur >= 0)
{
if (arr[cur]) arr[dest--] = arr[cur--];
else
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};3. 有效三角形的个数
思路：
首先对数组排序。
固定最短的两条边，二分查找最后一个小于两边之和的位置。可以求得固定两条边长之和满足条件的结果。枚举结束后，总和就是答案。
class Solution {
public:
int triangleNumber(vector<int>& nums) {
// 1. 排序来优化
sort(nums.begin(), nums.end());
// 2. 利用双指针来解决问题
int ret = 0, n = nums.size();
for (int i = n - 1; i >= 2; i--) // 先固定最大的数
{
// 利用双指针快速统计符合要求的三元组个数
int l = 0, r = i - 1;
while (l < r)
{
if (nums[l] + nums[r] > nums[i])
{
ret += r - l;
r--;
}
else l++;
}
}
return ret;
}
};4. 两数之和II
思路：
题目本质就是：查找和为 target 的两个数，由于已经是升序排列，直接双指针即可，left 指向0，right 指向 n -1 ，两数之后小于则 left ++，大于则 right --，相等就返回即可
注：返回的两个值，是从1开始计算，故需要加 1
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r)
{
if (nums[l] + nums[r] > target) r--;
else if (nums[l] + nums[r] < target) l++;
else return {l + 1, r + 1};
}
return {}; //若没有返回空即可
}
};
5、两数之和
思路：
该题与上一题有区别，是乱序的。为了使用左右端点双指针，需要排序，并且题目不是求结果而是求原索引，所以需要在排序前记录原索引。
因此我们使用先定义一个ind 数组，通过sort排序在ind数组中记录原数组中升序的索引排列，然后双指针即可。
注：返回时，小的索引在前，大的在后
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 1. 记录升序索引
int n = nums.size();
vector<int> ind(n); //下标数组
for (int i = 0; i < n; i++) ind[i] = i; //下标从 i 开始
sort(ind.begin(), ind.end(), [&](int i, int j)->bool{
return nums[i] < nums[j];
});
// 2. 双指针查找等于target 的两个ind 映射下标
int l = 0, r = n - 1;
while (nums[ind[l]] + nums[ind[r]] != target)
{
if (nums[ind[l]] + nums[ind[r]] > target) r--;
else if (nums[ind[l]] + nums[ind[r]] < target) l++;
}
// 3. 对两个ind 映射下标，小的数在前，大的数在后
if (ind[l] > ind[r]) swap(ind[l], ind[r]);
return {ind[l],ind[r]};
}
};6、三数之和
思路：
- 排序
- 固定一个数为 a （优化：固定的数a一定小于等于0，因为固定的a若是正数，其后面的数也是正数，三数之和一定不会等于0）
- 在该数后面区间内，利用双指针算法，找到两数之和等于 -a 即可，这里就可以用到上面题的写法了。
细节处理：
- 返回的是值不是下标
- 需要去重，做法：找到一种结果之和，left 和 right指针跳过重复元素，并且当使用完一次双指针之后，后面 i 往后移动也要跳过重复元素
- 避免指针越界
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> threeSum(vector<int>& nums) {
// 1. 排序
sort(nums.begin(), nums.end());
// 2. 利用双指针
int n = nums.size(), i = 0;
while (i < n) // 固定数 a
{
if (nums[i] > 0) break; // 优化
int l = i + 1, r = n - 1, target = -nums[i];
while (l < r)
{
if (nums[l] + nums[r] > target) r--;
else if (nums[l] + nums[r] < target) l++;
else
{
ans.push_back({ nums[i],nums[l],nums[r] });
// 缩小区间，去重left, right操作
l++, r--;
while (l < r && nums[l] == nums[l - 1]) l++;
while (l < r && nums[r] == nums[r + 1]) r--;
}
}
// 去重 i
i++;
while (i < n && nums[i] == nums[i - 1])i++;
}
return ans;
}
};
7、四数之和
思路
本题与「三数之和」相似，解法也相似。
注：需要避免溢出，因此求两个数的和是否为aim时，对aim需要 long long 强转
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// 1. 排序
sort(nums.begin(), nums.end());
int n = nums.size(), i = 0;
while(i < n)
{
// 利用三数之和
int j = i + 1;
while(j<n)
{
int l = j + 1, r = n - 1;
long long aim = (long long)target - nums[i] - nums[j]; //避免溢出
while (l < r)
{
if (nums[l] + nums[r] > aim) r--;
else if (nums[l] + nums[r] < aim) l++;
else
{
ans.push_back({ nums[i],nums[j],nums[l++],nums[r--] });
// 缩小区间，去重left, right操作
while (l < r && nums[l] == nums[l - 1]) l++;
while (l < r && nums[r] == nums[r + 1]) r--;
}
}
j++;
while (j < n && nums[j] == nums[j - 1]) j++;
}
i++;
while(i < n && nums[i] == nums[i - 1]) i++;
}
return ans;
}
};
