[LC优选算法#1] 双指针 | 移动零 | 复写零 | 快乐数 | 盛⽔最多的容器 | 有效三⻆形的个数 | 查找总价格为目标值的两个商品 | 三数之和 | 四数之和
·
目录
1. 双指针算法思想
这里的指针和C语言中存储地址的指针不同，更像是一种迭代器 / 下标的比喻。
常见的双指针分为快慢指针和对撞指针：
- 快慢指针：使用两个移动速度不同的指针在数组 / 链表结构上移动。
- 对撞指针：两个指针分别从顺序结构的两端出发，向中间移动。
2. 经典例题
2.1 移动零
2.1.1 解题思路
- 暴力：遍历数组，每次将0元素删除并尾插到数组末尾，涉及到插入删除时间复杂度过高，不推荐。
- 双指针O(N)：利用快速排序的思想，设置两个指针 cur 和 dest ，将数组分为 [0, dest] 和 [cur, n - 1] 两个部分，前半部分是已经移动过的元素（除了dest位置），后半部分是还未移动的元素。如果cur指向的是0，就跳过；否则交换cur和dest位置的元素。
易错点：
- 注意自己的dest指针指向的是有效元素还是有效元素的下一个位置！
2.1.2 代码展示
// 双指针
class Solution {
public:
void moveZeroes(vector<int>& nums)
{
for(int cur=0, dest =-1; cur<nums.size(); cur++)
{
if(nums[cur] != 0)
{
dest++;
swap(nums[cur], nums[dest]);
}
}
}
};2.2 复写零
2.2.1 解题思路
- 插入法O(N^2)：遇到0则在下一个位置插入0，直到元素个数和原数组的元素个数相同。
- 双指针O(N)：如果从前往后复写，会导致后面的数被覆盖，因此选择从后往前复写：
step1：设置两个指针dest和cur从前往后移动，cur用于遍历数组元素，dest记录复写零后的实时元素位置，直至到数组末尾
step2：cur和dest指针从后往前移动，遇到非0元素则交换cur和dest的值，遇到0则dest向前走2步，设置为0，直至数组起始位置为止。
一去一回，时间花费共2*N，时间复杂度为O(N)。
易错点：
- 双指针越界问题：在step1中，如果cur位置为0，且dest位于倒数第二个元素，那么移动dest会发生越界，需要优先处理最后的0元素再开始step2。
- 插入法迭代器失效：在遇到0并插入后，i的位置需要移动到第二个0的位置，再由for循环移动到下一个元素位置。
2.2.2 代码展示
//插入法
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
int n = arr.size();
for(int i=0; i<n; i++)
{
if(arr[i] == 0)
{
arr.insert(arr.begin()+i, 0);
i++; //更新迭代器
}
}
arr.resize(n);
}
};//双指针
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
int n = arr.size();
int cur = 0;
int dest = -1;
while(cur < n)
{
if(arr[cur] == 0)
{
dest += 2;
}
else
{
dest++;
}
if(dest >= n - 1)
{
break;
}
cur++;
}
if(dest > n - 1) //越界问题
{
arr[n - 1] = 0;
dest -= 2;
cur--;
}
while(dest >= 0)
{
if(arr[cur] == 0)
{
arr[dest] = 0;
arr[dest - 1] = 0;
dest -= 2;
}
else
{
arr[dest] = arr[cur];
dest--;
}
cur--;
}
}
};2.3 快乐数
2.3.1 解题思路
- 计算小巧思（特解）O(N)：计算1~9可知，只有1和7是快乐数。因此可以设置循环的结束条件是n<10，在循环外判断n是否为1或7，是则为快乐数，反之不是。
- 双指针O(N)：和带环链表思路类似，设置快慢指针，fast走两步，slow走一步，由于快慢指针速度差为1个单位，因此fast和slow一定会相遇。因为无论是快乐数还是非快乐数，都会进入循环，因此可以根据相遇点是否为1来判断是否为快乐数：
两个指针分别遍历了常数次数组，时间复杂度为O(N)。
2.3.2 代码展示
//计算小巧思
class Solution {
public:
bool isHappy(int n)
{
while(n >= 10)
{
int num = n;
long long sum = 0;
while(num)
{
sum += (num % 10) * (num % 10);
num /= 10;
}
n = sum;
}
if(n == 1 || n == 7) //个位只有1和7是快乐数
{
return true;
}
return false;
}
};//双指针
class Solution {
public:
long long culSum(int num) //封装计算函数
{
int sum = 0;
while(num)
{
long long a = num % 10;
sum += a*a;
num /= 10;
}
return sum;
}
bool isHappy(int n)
{
long long slow = n;
long long fast = culSum(n);
while(slow != fast)
{
slow = culSum(slow); //慢指针计算一次
fast = culSum(culSum(fast)); //快指针计算两次
}
return slow == 1;
}
};2.4 盛⽔最多的容器
2.4.1 解题思路
- 暴力O(N^2)：双层嵌套for循环，无脑枚举所有的体积，记录最大值。
- 双指针O(N)：设置对撞指针left和right，从首尾出发，计算指针对应元素之间的体积，然后比较两个指针的值，固定较大元素指针，较小元素的指针向中间移动。再次计算，直至两指针相遇，即可得出最大的体积。
两个指针共遍历一次数组，时间复杂度为O(N)。
Q：为什么要让指向较小元素的指针向中间移动？
A：因为较小元素在范围内无论怎样枚举都会使体积变小，可以直接舍去。
假设有数组 { 6，2，5，4 } ，当计算完6和4之间的体积后，如果固定4不动向内枚举：
情况1：枚举到比4小的元素（2），这时体积的宽和高都减少，体积变小。
情况2：枚举到大于等于4的元素（5），这时无论这个元素有多大，高度始终被限制在4不变，宽度减少，体积也会变小。
2.4.2 代码展示
//暴力（超时）
class Solution {
public:
int maxArea(vector<int>& height)
{
int n = height.size();
int maxx = 0;
for(int i=0; i<n-1; i++)
{
for(int j=i+1; j<n; j++)
{
int tmp = (j-i) * min(height[j], height[i]);
maxx = max(maxx, tmp);
}
}
return maxx;
}
};//双指针
class Solution {
public:
int maxArea(vector<int>& height)
{
int n = height.size();
int left = 0;
int right = n - 1;
int maxv = 0;
while(left < right)
{
maxv = max(maxv, min(height[left], height[right]) * (right - left));
//较小的向内移动
if(height[left] < height[right])
{
left++;
}
else
{
right--;
}
}
return maxv;
}
};2.5 有效三⻆形的个数
2.5.1 解题思路
- 暴力O(NlogN + N^3)：将数组排序，用三层嵌套for循环枚举所有的三边，统计能组成三角形的数据组数量。
- 双指针O(NlogN + N^2)：将数组排序，利用单调性+双指针的方法统计三角形个数：
step1：数组排序
step2：固定一个最大的边
step3：在最大边的左区间内，用双指针算法找出剩下符合要求的两边。循环step2，3统计符合条件的三边。
双指针算法：设置left和right指针位于范围的两端，如果指针的元素之和小于等于固定的最大边，说明范围内的元素和left组合都不能满足三角形，舍去并将left指针向内移动；如果指针的元素之和大于固定的边，说明范围内的数和right组合都能满足三角形，统计入个数并将right的指针向内移动，直至指针相遇 / 不能构成三角形。
数组排序需要NlogN，对每条边进行双指针遍历，时间近似为N*N，故时间复杂度为O(NlogN + N^2)。
2.5.2 代码展示
//暴力
class Solution {
public:
int triangleNumber(vector<int>& nums)
{
sort(nums.begin(), nums.end());
int cnt = 0;
int n = nums.size();
for(int i=0; i<n-2; i++)
{
for(int j=i+1; j<n-1; j++)
{
int gap = j + 1;
while(gap < n && nums[i] + nums[j] > nums[gap])
{
cnt++;
gap++;
}
}
}
return cnt;
}
};//双指针
class Solution {
public:
int triangleNumber(vector<int>& nums)
{
sort(nums.begin(), nums.end());
int cnt = 0;
// 固定一条边
for(int i=nums.size()-1; i>=2; i--)
{
// 双指针遍历这条边之前的元素
int left = 0;
int right = i-1;
while(left < right)
{
if(nums[left] + nums[right] > nums[i])
{
cnt += right - left;
right--;
}
else
{
left++;
}
}
}
return cnt;
}
};2.6 查找总价格为目标值的两个商品
2.6.1 解题思路
- 暴力O(N^2)：两层嵌套for循环枚举所有加和的情况，会超时，不推荐。
- 双指针O(N)：由于数组已经有序，可以设置对撞指针left和right从数组两端开始，如果和偏大则移动右指针，和偏小则移动左指针，直至和相等 / 两指针相遇为止。
最坏情况是左右指针共同遍历一次数组，因此时间复杂度是O(N)。
2.6.2 代码展示
//双指针
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target)
{
vector<int> ret;
int left = 0;
int right = price.size() - 1;
while(left < right)
{
if(price[left] + price[right] < target) //偏小
{
left++;
}
else if(price[left] + price[right] > target) //偏大
{
right--;
}
else
{
ret.push_back(price[left]);
ret.push_back(price[right]);
break;
}
}
return ret;
//或者不用创建数组，直接返回：return {price[left], price[right]};
}
};
2.7 三数之和
2.7.1 解题思路
- 暴力O(NlogN + N^3)：将数组排序，用三层嵌套for循环暴力枚举，得出符合条件的所有三数组合，存入set中去重。
- 双指针O(NlogN + N^2)：将数组排序，一层for循环枚举数组中的元素x，再在该元素之后的范围内用对撞指针，转化为求两个和为-x的元素组合（类似2.6解法）。
排序的时间复杂度为O(NlogN)；循环需要遍历一次数组，循环内部还要对每个元素进行指针对撞，相当于遍历N次数组，最坏情况的时间消耗为N*N；因此总的时间复杂度为O(NlogN + N^2)。
易错点：
因为题目中要求返回所有不重复的三数组合，因此需要在题2.6的基础上进行继续枚举+去重操作：
- 继续枚举：当left和right找到了符合条件的元素组合，不能直接进入下一次循环，还需要继续查找直至指针相遇，这样才不会遗漏组合。
- 去重操作：去重分为对for循环中枚举的元素x去重和对left和right指向的元素进行去重。如果当前数和下一个数相同，则跳过下一个数。
另外，去重的操作需要额外注意迭代器的移动！避免越界 / 跳过！
2.7.2 代码展示
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums)
{
sort(nums.begin(), nums.end());
vector<vector<int>> vv;
int n = nums.size();
for(int i=0; i<n-2; i++)
{
int left = i+1;
int right = n-1;
int flag = 0;
while(left < right)
{
if(nums[left] + nums[right] == -nums[i])
{
flag = 1;
vv.push_back({nums[left], nums[right], nums[i]});
left++;
right--;
//去重left和right
while(left < right && nums[left-1] == nums[left])
{
left++;
}
while(left < right && nums[right+1] == nums[right])
{
right--;
}
}
else if(nums[left] + nums[right] > -nums[i])
{
right--;
}
else
{
left++;
}
}
//去重i
if(flag == 1)
{
while(i < n-2 && nums[i] == nums[i+1])
{
i++;
}
}
}
return vv;
}
};
2.8 四数之和
2.8.1 解题思路
- 暴力O(NlogN + N^4)：将数组排序，用四层嵌套for循环暴力枚举，得出符合条件的所有三数组合，存入set中去重。
- 双指针O(NlogN + N^3)：将数组排序，一层for循环枚举数组中的元素a，转化为求三个和为target-a的元素组合（类似2.7三数之和解法）。
排序的时间复杂度为O(NlogN)；枚举需要两个嵌套for循环，循环内部还要对每个元素进行指针对撞，相当于遍历N次数组，最坏情况的时间消耗为N*N*N；因此总的时间复杂度为O(NlogN + N^3)。
易错点：
注意去重有三处：元素a，元素x，还有左右指针left和right指向的元素。
容易发生数组越界问题，注意迭代器的移动！
2.8.2 代码展示
//双指针
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target)
{
vector<vector<int>> vv;
sort(nums.begin(), nums.end());
long long n = nums.size();
for(int i=0; i<n-3; i++)
{
long long out = target - nums[i];
for(int j=i+1; j<n-2; j++)
{
int left = j+1;
int right = n-1;
while(left < right)
{
long long sum = nums[left] + nums[right];
if(sum < out - nums[j])
{
left++;
}
else if(sum > out - nums[j])
{
right--;
}
else
{
vv.push_back({nums[left], nums[right], nums[j], nums[i]});
left++;
right--;
//去重
while(left < right && nums[left-1] == nums[left])
{
left++;
}
//去重
while(left < right && nums[right+1] ==nums[right])
{
right--;
}
}
}
//去重
while(j < n-1 && nums[j+1] == nums[j])
{
j++;
}
}
//去重
while(i < n-1 && nums[i+1] == nums[i])
{
i++;
}
}
return vv;
}
};3. 总结
双指针优化的核心条件：
在有序或满足某种单调性（单调和、单调差、单调乘积）的数据结构上，两个指针的移动方向是单向的（不回退）。
经典题型中，双指针优化的标志性特征：
-
数组有序
-
要找“和 / 差 / 积”满足某个条件
-
暴力是两层 for 循环
Q：什么时候双指针优化不了？
A：出现以下几种情况时：
-
数组无序
-
没有单调性（比如要求元素乘积 = target，但数组有正有负，乘积不单调）
-
不是“比较两个元素”，而是要在子区间里取任意组合（比如子集的和问题）
双指针是由暴力算法优化而来的，在解题时应该优先通过暴力算法来寻找对应的优化算法。另外，建议在遇到类似的题后不要想当然的用双指针，一定要先画图证明双指针的可行性。
//欢迎互三(☆▽☆)！
更多推荐
29
0- 0
已为社区贡献5条内容
所有评论(0)