双指针
2026-02-21 16:06:11
发布于：浙江
5阅读
0回复
0点赞
来讲一讲双指针吧。
双指针是一种比较常见的优化手段。
一般用于将O(n^2)时间复杂度优化成O(n)。
这里拿一道题目举例：最大子段和
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;//不开long long 见祖宗
ll a[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int r=0;//这里r的定义需要非常明确。
//我对r的定义是：已经加过的数的下标
ll ans=-1e18;//请注意，这里answer的最小值不是0，请尽量开到最小。
ll s=0;//不开long long 见祖宗
for(int l=1;l<=n;l++){
s-=a[l-1];
while(r<l)s+=a[++r];//很容易把这边漏掉。因为子序列不能为空。至少得把当前的自己加上。
ans=max(ans,s);//实时更新ans，因为s的定义不是最大值。它只是一个更新的容器
while(r+1<=n&&s+a[r+1]>=0){
s+=a[++r];
ans=max(ans,s);
}
}
cout<<ans;
return 0;
}
/*
题目总结：
无论在进行复杂代码还是简单代码的编写时，都需要对每个变量的定义
有着清晰的认知，这样一来，不但方便对后续代码的编写，也可以大大减少
提示的时间。（翻译：脑子不清楚点你就完蛋了。
双指针，就是人遛狗。人规律地一步步往前走。狗随着人一步步往前走，自己
一跳一跳地不规律地往前奔。都在向前。
一个指针在for循环里，另一个指针在for循环外。
都只加不减。到n停止。你需要做的就是创造出能使两个指针都只加不减的环境。
*/
这里空空如也
有帮助，赞一个